题目描述

给你一个正整数 $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)$ 的矩形区域中所含整数的最大公约数。

输入格式

第一行输入 $N$ $Q$

第二行输入 $A_1$ $A_2$ $\dots$ $A_N$

第三行输入 $B_1$ $B_2$ $\dots$ $B_N$

接下来 $Q$ 次查询，每次输入 $h_1$ $h_2$ $w_1$ $w_2$

输出格式

输出一共输出 $Q$ 行。

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

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$