33267번 - Huge Sequences 다국어

Given three sequences $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $c_1, \ldots, c_n$, define the value of the interval $[\ell, r]$ as the product of three factors:

• the bitwise AND of $(a_{\ell}, \ldots, a_{r})$,
• the bitwise OR of $(b_{\ell}, \ldots, b_{r})$, and
• the greatest common divisor of $(c_{\ell}, \ldots, c_{r})$.

There are $m$ queries. Each query provides an interval $[\ell, r]$, and asks for the sum of the values of all intervals $[\ell', r']$ such that $\ell \le \ell' \le r' \le r$. As the answer may be large, find it modulo $2^{32}$.

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 10^6$; $1 \le m \le 5 \cdot 10^6$).

The second line contains $n$ integers $a_1, \ldots, a_n$.

The third line contains $n$ integers $b_1, \ldots, b_n$.

The fourth line contains $n$ integers $c_1, \ldots, c_n$.

The constraints are: $1 \le a_i, b_i, c_i \le n$.

Each of the following $m$ lines contains two integers $\ell$ and $r$ and represents a query ($1 \le \ell \le r \le n$).

Output $m$ lines, each containing one integer: the corresponding answer modulo $2^{32}$.