C. The Thermotaur Labyrinth
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Have you ever heard of the Thermotaur Labyrinth? It is a square, single-story building partitioned into identical square rooms. However, it is not quite a labyrinth — one can move from any room to any adjacent room on a side, but no one can exit the boundaries of the labyrinth. Each room has a distinct temperature, which can vary from one room to another.

A Mad Scientist conducts experiments on minotaurs within this Thermotaur Labyrinth. He releases them one by one into specific rooms and observes where they ultimately go. It turns out that minotaurs do not favor high temperatures; thus, they will always leave their current room for an adjacent room with the lowest temperature. Naturally, if all adjacent rooms have a higher temperature than their current one, the minotaur will choose to remain in its current room.

Upon learning about the experiments of the Mad Scientist and the minotaurs' behavior, you took pity on them and declared that you could write a program that determines the final room that a minotaur will occupy, given any starting position.

Input

The first line of the input contains the size of the labyrinth $$$N$$$ ($$$1 \leq N \leq 500$$$). The following $$$N$$$ lines each contain $$$N$$$ integers — representing the temperatures of the rooms in the labyrinth. All temperatures are distinct positive integers, not exceeding $$$N^2$$$.

The next line contains the number of queries $$$Q$$$ ($$$1 \leq Q \leq 20\,000$$$). Each of the following $$$Q$$$ lines contains two integers indicating the row and column of the room where the minotaur is initially placed.

Output

For each query, output on a separate line the temperature of the room where the minotaur ultimately comes to rest.

Example
Input
4
1 2 3 4
7 14 12 11
6 13 10 15
5 8 9 16
7
1 1
1 4
2 1
3 1
4 4
3 3
2 3
Output
1
1
1
5
5
5
1