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 \bmod M~, 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