GCD

Time limit: 4.0s , Memory limit: 512M , Points: 2500 (partial)

Cho hai mảng số nguyên dương $a$ ~a~ và $b$ ~b~ gồm $n$ ~n~ phần tử được đánh số từ $1$ ~1~ đến $n$ ~n~.

Cho ma trận $X$ ~X~ kích thước $n \times n$ ~n \times n~, các cột được đánh số từ $1$ ~1~ đến $n$ ~n~ từ trên xuống dưới và các hàng được đánh số từ $1$ ~1~ đến $n$ ~n~ từ trái sang phải. Mỗi phần tử $X_{i,j}$ ~X_{i,j}~ của ma trận được tính bởi công thức:

$X_{i,j}=a_i+b_j$

Thực hiện $q$ ~q~ truy vấn, mỗi truy vấn bao gồm bốn số nguyên $r_1,r_2,c_1,c_2$ ~r_1,r_2,c_1,c_2~ $(1 \le r_1 \le r_2 \le n$ ~(1 \le r_1 \le r_2 \le n~ ; $1 \le c_1 \le c_2 \le n)$ ~1 \le c_1 \le c_2 \le n)~, yêu cầu tính giá trị ước chung lớn nhất của các phần tử ma trận nằm trong hình chữ nhật có góc trái trên $(r_1,c_1)$ ~(r_1,c_1)~ và góc phải dưới $(r_2,c_2)$ ~(r_2,c_2)~, hay nói cách khác, yêu cầu tính $gcd(X_{i,j})$ ~gcd(X_{i,j})~ với $r_1 \le i \le r_2, c_1 \le j \le c_2$ ~r_1 \le i \le r_2, c_1 \le j \le c_2~.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $q$ ~q~ $(1 \le n,q \le 10^6)$ ~(1 \le n,q \le 10^6)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên của mảng $a$ ~a~ $(1 \le a_i \le 10^9)$ ~(1 \le a_i \le 10^9)~.
Dòng thứ ba chứa $n$ ~n~ số nguyên của mảng $b$ ~b~ $(1 \le b_j \le 10^9)$ ~(1 \le b_j \le 10^9)~.
$q$ ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $r_1,r_2,c_1,c_2$ ~r_1,r_2,c_1,c_2~ mô tả truy vấn.

Output

Với mỗi truy vấn, in ra ước chung lớn nhất của các phần tử ma trận trên một dòng.

Examples

Sample Input

5 3
2 4 8 8 1
4 8 12 16 1
2 3 1 2
1 2 2 4
1 5 1 5

Sample Output

4
2
1

Scoring

Subtask $1$ ~1~ $-$ ~-~ $500$ ~500~ điểm: $n,q \le 100$ ~n,q \le 100~
Subtask $2$ ~2~ $-$ ~-~ $500$ ~500~ điểm: $n \le 2000$ ~n \le 2000~ ; $a_i\le 3$ ~a_i\le 3~ với mọi $1 \le i \le m$ ~1 \le i \le m~ ; $b_j \le 3$ ~b_j \le 3~ với mọi $1 \le j \le n$ ~1 \le j \le n~
Subtask $3$ ~3~ $-$ ~-~ $500$ ~500~ điểm: $b_i=b_j$ ~b_i=b_j~ với mọi $1 \le i < j \le n$ ~1 \le i < j \le n~
Subtask $4$ ~4~ $-$ ~-~ $500$ ~500~ điểm: $r_1=r_2$ ~r_1=r_2~ với mọi truy vấn
Subtask $5$ ~5~ $-$ ~-~ $500$ ~500~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, với $a=[2,4,8,8,1]$ ~a=[2,4,8,8,1]~ và $b=[4,8,12,16,1]$ ~b=[4,8,12,16,1]~, ma trận $X$ ~X~ được xây dựng như sau:

$X = \left( \begin{array}{cc} 2+4 & 2+8 & 2+12 & 2+16 & 2+1\\ 4+4 & 4+8 & 4+12 & 4+16 & 4+1\\ 8+4 & 8+8 & 8+12 & 8+16 & 8+1\\ 8+4 & 8+8 & 8+12 & 8+16 & 8+1\\ 1+4 & 1+8 & 1+12 & 1+16 & 1+1 \end{array} \right) = \left( \begin{array}{cc} 6 & 10 & 14 & 18 & 3\\ 8 & 12 & 16 & 20 & 5\\ 12 & 16 & 20 & 24 & 9\\ 12 & 16 & 20 & 24 & 9\\ 5 & 9 & 13 & 17 & 2 \end{array} \right)$

Ở truy vấn thứ nhất, $gcd(X_{i,j}) = gcd(X_{2,1},X_{2,2},X_{3,1},X_{3,2}) = gcd(8,12,12,16) = 4$ .

GCD