## Magic Maze

View as PDF

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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

#### 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

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

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

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