题目背景

 何もいらない
 不再奢求什么
 あなたがいればいい
 只要有相伴
 そっと橫顏 息を殺す
 悄悄地侧着脸 屏住呼吸
 まばたきすれば
 似乎一眨眼
 消えてしまいそうで
 就会突然消失一般
 凝視(みつ)めさせて 好きだよ
 凝视着我喜欢的你

 あぁ 木々が震え 降り出した雪
 啊啊 树影摇曳 落雪纷纷
 足跡 ふたつ 白く
 唯留两行白色的足迹
 時よ 積もれ
 时光 点点堆积
 時よ 積もれ
 时光 点点堆积
 髪に 胸に ふたりだけの夢に
 在发间 在心中 只属于你我的梦中
 咲けない花の種は
 无法开出花朵的种子
 雪に抱かれ 寄り添うの
 在雪的怀抱中 相依相偎
 靜かに忘れられたい
 只想静静地被遗忘

题目描述

给序列 $a_1,\dots,a_n$，$b_1,\dots,b_n$，$c_1,\dots,c_n$，

定义区间 $[l,r]$ 的价值为 $a_l,\dots,a_r$ 按位与，$b_l,\dots,b_r$ 按位或，$c_l,\dots,c_r$ 的最大公因数，这三者的乘积；

$m$ 次查询，每次查询给出区间 $[l,r]$，查询满足 $l\le l'\le r'\le r$ 的 $[l',r']$ 的价值之和。

输入格式

第一行两个整数 $n,m$；

第二行 $n$ 个整数 $a_1,\dots,a_n$；

第三行 $n$ 个整数 $b_1,\dots,b_n$；

第四行 $n$ 个整数 $c_1,\dots,c_n$；

接下来 $m$ 行，每行两个整数 $l,r$ 表示一次查询。

输出格式

共 $m$ 行，每行一个整数，表示对应的答案，答案对 $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

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足

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

建议使用高效的输入输出方式。