Magic Maze

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Java 8 2.5s
PyPy 2 2.5s
PyPy 3 2.5s
Memory limit: 512M

Author:
Problem type

Naofumi is exploring a magical maze! The maze is a 2-D array with N×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 Ri×Cj. 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 Ri×CjmodM, where M is any prime number Naofumi chooses. Being the observant person he is, Naofumi has Q queries containing 4 integers ra,ca,rb,cb. For each query, he wants you to find out the maximum prime M he can choose such that there is a valid path from (ra,ca) to (rb,cb), 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 Ri, representing the array R.

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

The next Q lines will each contain 4 integers ra,ca,rb,cb, representing a query from (ra,ca) to (rb,cb).

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

1N105

1Q105

1Ri,Cj1000

1ra,ca,rb,cbN

rarb

cacb

Subtask 1 [20%]

1N100

1Q100

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


  • 5
    Aaeria  commented on Nov. 6, 2019, 8:52 p.m. edit 3

    It is a bit unclear but Naofumi can only use 1 value of M per query.