矩形 GCD

题目描述

给定一个正整数 $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)$。对每个满足 $1 \le i,j \le N$ 的整数对 $(i,j)$，格子 $(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)$ 分别为左上角和右下角的矩形区域所含整数的最大公约数。

输入格式

输入按以下格式从标准输入给出：

N Q
A_1 A_2 … A_N
B_1 B_2 … B_N
query_1
query_2
⋮
query_Q

每个查询的格式如下：

h_1 h_2 w_1 w_2

输出格式

输出 $Q$ 行。第 $i$ 行应输出 $\mathrm{query}_i$ 的答案。

样例

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

2
1
11
6
10

记格子 $(i,j)$ 上的整数为 $C_{i,j}$。

对于第 1 个查询，有 $C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8$，所以答案是它们的最大公约数，即 2。

1 1
9
100
1 1 1 1

109

数据范围

• $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$
• 输入中的所有值均为整数。