거대한 수열

세 수열 $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, $c_1, \ldots, c_n$이 주어진다. 구간 $[\ell, r]$의 값은 세 값의 곱이다. 세 값은 각각 $a_\ell, \ldots, a_r$의 비트 AND, $b_\ell, \ldots, b_r$의 비트 OR, $c_\ell, \ldots, c_r$의 최대공약수이다.

질의가 $m$개 주어진다. 각 질의는 구간 $[\ell, r]$을 나타내며, $\ell \le \ell' \le r' \le r$을 만족하는 모든 구간 $[\ell', r']$의 값을 더한 합을 구한다. 답은 $2^{32}$로 나눈 나머지로 출력한다.

첫째 줄에 두 정수 $n$, $m$이 주어진다 ($1 \le n \le 10^6$, $1 \le m \le 5 \cdot 10^6$).

둘째 줄에는 $n$개의 정수 $a_1, \ldots, a_n$이 주어진다.

셋째 줄에는 $n$개의 정수 $b_1, \ldots, b_n$이 주어진다.

넷째 줄에는 $n$개의 정수 $c_1, \ldots, c_n$이 주어진다. 모든 $a_i$, $b_i$, $c_i$는 $1 \le a_i, b_i, c_i \le n$을 만족한다.

이후 $m$개의 줄에는 질의를 나타내는 두 정수 $\ell$, $r$이 주어진다 ($1 \le \ell \le r \le n$).

$m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 $2^{32}$로 나눈 나머지를 출력한다.