Background

 I do not need anything.
 I no longer ask for anything.
 As long as you are here, it is enough.
 As long as we are together.
 Quietly turning my face aside, holding my breath.
 It feels like, if I blink,
 you might suddenly disappear.
 So let me keep staring; I like you.

 Ah, the trees tremble, and the snow begins to fall.
 Only two lines of white footprints remain.
 Time, pile up.
 Time, pile up.
 In my hair, in my chest, in the dream that belongs only to the two of us,
 the seeds of a flower that cannot bloom
 snuggle close, embraced by the snow.
 I just want to be quietly forgotten.

Problem Description

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

Define the value of an interval $[l,r]$ as the product of the following three quantities: 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 gives an interval $[l,r]$. For each query, compute the sum of the values of all sub-intervals $[l',r']$ that satisfy $l \le l' \le r' \le r$.

Input Format

The first line contains two integers $n,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,r$, representing one query.

Output Format

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

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

48
63
24

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $100\%$ of the testdata, it holds that:

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

Efficient I/O is recommended.

Translated by ChatGPT 5