Naofumi is exploring a magical maze! The maze is a 2-D array with
pillars. The height of each pillar is generated using two arrays
and
, each of size
. Specifically, the height of the pillar at row
and column
, pillar
, would be
. 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
. 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
, where
is any prime number Naofumi chooses. Being the observant person he is, Naofumi has
queries containing
integers
. For each query, he wants you to find out the maximum prime
he can choose such that there is a valid path from
to
, 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
integers
and
, representing the dimensions of the grid and the number of queries.
The second line will contain
integers
, representing the array
.
The third line will contain
integers
, representing the array
.
The next
lines will each contain
integers
, representing a query from
to
.
Output Specification
The output should contain
integers, each on a separate line, representing the maximum prime
that can be used to create a valid path for the corresponding query. If no such
exists, print -1
.
Constraints






Subtask 1 [20%]


Subtask 2 [80%]
No additional constraints.
Sample Input
Copy
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
Copy
2
3
-1
Visualization of Sample Input
 |
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 |
Comments
It is a bit unclear but Naofumi can only use 1 value of
per query.