P9335 [Ynoi2001] Flowers Blooming in the Snow

 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. 

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

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 $m$ lines, each containing one integer representing the corresponding answer. Output the answer modulo $2^{32}$.

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