Given sequences $a_1, \dots, a_n$, $b_1, \dots, b_n$, and $c_1, \dots, c_n$.

Define the value of an interval $[l, r]$ as the product of the bitwise AND of $a_l, \dots, a_r$, the bitwise OR of $b_l, \dots, b_r$, and the greatest common divisor of $c_l, \dots, c_r$.

There are $m$ queries. Each query provides an interval $[l, r]$, and you are asked to find the sum of the values of all intervals $[l', r']$ such that $l \le l' \le r' \le r$.

Input

The first line contains two integers $n$ and $m$.

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

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

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

The next $m$ lines each contain two integers $l$ and $r$, representing a query.

$1 \le n \le 10^6$

$1 \le m \le 5 \times 10^6$

$1 \le a_i, b_i, c_i \le n$

$1 \le l \le r \le n$

Output

Output $m$ lines, each containing an integer representing the corresponding answer.

The answer should be output modulo $2^{32}$.

Examples

Input 1

5 3
3 3 1 1 1
2 1 3 2 2
4 5 3 4 4
1 2
2 5
4 5

Output 1

48
63
24

Note

It is recommended to use efficient input and output methods.