Huge Sequences

You are given three sequences $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $c_1, \ldots, c_n$. The value of an interval $[\ell, r]$ is 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 gives an interval $[\ell, r]$ and asks for the sum of the values of all intervals $[\ell', r']$ with $\ell \le \ell' \le r' \le r$. Report each answer modulo $2^{32}$.

The first line 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$. Every $a_i$, $b_i$, and $c_i$ satisfies $1 \le a_i, b_i, c_i \le n$.

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

Print $m$ lines. The $i$-th line contains the answer to the $i$-th query modulo $2^{32}$.