分数: 500 点
问题陈述
给你一个正整数 N 和序列 N 正整数: A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N).
我们有一个 N \times N 网格。广场位于 i从顶部开始的第行和 j从左边算起的第列称为正方形 (i,j)。对于每对整数 (i,j) 这样 1 \le i,j \le N,正方形 上面写着 (i,j) 具有整数 上面写着 A_i + B_j 。工艺流程 Q 以下形式的查询。
- 给你一个四倍整数 h_1,h_2,w_1,w_2 这样 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N。求左上角和右下角的矩形区域中包含的整数的最大公约数 分别为 (h_1,w_1) 和 (h_2,w_2)。
约束
- 1 \le N,Q \le 2 \times 10^5
- 1 \le A_i,B_i \le 10^9
- 1 \le h_1 \le h_2 \le N
- 1 \le w_1 \le w_2 \le N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均采用以下格式:
h_1 h_2 w_1 w_2
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 \mathrm{query}_i.
示例输入 1
3 5 3 5 2 8 1 3 1 2 2 3 1 3 1 3 1 1 1 1 2 2 2 2 3 3 1 1
示例输出 1
2 1 11 6 10
让 C_{i,j} 表示正方形上的整数 (i,j).
对于 1-st 查询,我们有 C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8,所以答案是它们的最大公约数,即 2.
示例输入 2
1 1 9 100 1 1 1 1
示例输出 2
109