Problem Statement
You are given a positive integer N and sequences of N positive integers each: A=(A1,A2,dots,AN) and B=(B1,B2,dots,BN).
We have an NtimesN grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1lei,jleN, the square (i,j) has the integer Ai+Bj written on it. Process Q queries of the following form.
- You are given a quadruple of integers h1,h2,w1,w2 such that 1leh1leh2leN,1lew1lew2leN. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h1,w1) and (h2,w2), respectively.
Constraints
- 1leN,Qle2times105
- 1leAi,Bile109
- 1leh1leh2leN
- 1lew1lew2leN
- All values in input are integers.
Input is given from Standard Input in the following format:
N Q
A1 A2 dots AN
B1 B2 dots BN
mathrmquery1
mathrmquery2
vdots
mathrmqueryQ
Each query is in the following format:
h1 h2 w1 w2
Output
Print Q lines. The i-th line should contain the answer to mathrmqueryi.
Sample Output 1
Let Ci,j denote the integer on the square (i,j).
For the 1-st query, we have C1,2=4,C1,3=6,C2,2=6,C2,3=8, so the answer is their greatest common divisor, which is 2.
Sample Output 2