Naofumi is exploring a magical maze! The maze is a 2-D array with $N\times N$ pillars. The height of each pillar is generated using two arrays $R$ and $C$, each of size $N$. Specifically, the height of the pillar at row $i$ and column $j$, pillar $(i,j)$, would be $R_i\times C_j$. A path in this maze is defined as a sequence of pillars where every successive pillar is below or to the right of the previous pillar (i.e. only moving down or to the right). A valid path is defined as a path where the height of each pillar in the path is $0$. To help him reduce the height of the pillars, Naofumi has a magical modulus spray, allowing him to reduce the height of each pillar to $R_i\times C_{j}modM$, where $M$ is any prime number Naofumi chooses. Being the observant person he is, Naofumi has $Q$ queries containing $4$ integers $r_a,c_a,r_b,c_b$. For each query, he wants you to find out the maximum prime $M$ he can choose such that there is a valid path from $(r_a,c_a)$ to $(r_b,c_b)$, or determine that it is impossible to create a valid path. Note that he does not actually use the spray after you answer a query. Can you help him find these values?

Input Specification

The first line will contain $2$ integers $N$ and $Q$, representing the dimensions of the grid and the number of queries.

The second line will contain $N$ integers $R_i$, representing the array $R$.

The third line will contain $N$ integers $C_j$, representing the array $C$.

The next $Q$ lines will each contain $4$ integers $r_a,c_a,r_b,c_b$, representing a query from $(r_a,c_a)$ to $(r_b,c_b)$.

Output Specification

The output should contain $Q$ integers, each on a separate line, representing the maximum prime $M$ that can be used to create a valid path for the corresponding query. If no such $M$ exists, print -1.

Constraints

$1\le N\le {10}^5$

$1\le Q\le {10}^5$

$1\le R_i,C_j\le 1000$

$1\le r_a,c_a,r_b,c_b\le N$

$r_a\le r_b$

$c_a\le c_b$

Subtask 1 [20%]

$1\le N\le 100$

$1\le Q\le 100$

Subtask 2 [80%]

No additional constraints.

Sample Input

5 3
2 3 1 4 3
3 4 2 6 5
1 2 3 2
2 2 3 4
3 4 3 5

Sample Output

2
3
-1

Visualization of Sample Input

$\times$	3	4	2	6	5
2	6	8	4	12	10
3	9	12	6	18	15
1	3	4	2	6	5
4	12	16	8	24	20
3	9	12	6	18	15