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

Problem type

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.


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


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


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

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