Naofumi is exploring a magical maze! The maze is a 2D 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 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 , where is any prime number Naofumi chooses. Being the observant person he is, Naofumi has queries containing 4 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?
The first line will contain 2 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 4 integers , representing a query from to .
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
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
5 3 2 3 1 4 3 3 4 2 6 5 1 2 3 2 2 2 3 4 3 4 3 5
2 3 -1
Visualization of Sample Input