题目描述

给定一个正整数 $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$ 行应包含第 $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)$ 上的整数。

对于第一个查询，我们有 $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