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}$.

제한

힌트