D. Machu Picchu
time limit per test
2.5 s
memory limit per test
256 MB
input
standard input
output
standard output

The high elevations of Machu Picchu can cause altitude sickness. Tourists, such as Gennady Korotkevich, plan to hike to the various attractions at Machu Picchu; each wants to visit a certain number of attractions but cannot exceed their personal elevation capacity (or "peak rating") at any point along their hike.

Tourists can only move one tile north, south, east, or west, to a height that has a difference of at most $$$1$$$ from their current height.

Fortunately, the tour sponsors have made it possible for each tourist to begin their hike anywhere in Machu Picchu. Help each tourist find the best coordinates to start their hike!

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 1000)$$$, representing the number of rows and columns of an elevation map describing the region.

The next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$ -th number in the $$$i$$$ -th row represents the elevation of coordinate $$$(i, j)$$$. It is guaranteed that the elevation of each coordinate does not exceed $$$10^5$$$.

The next line contains a single integer $$$a$$$ $$$(1 \leq a \leq 10)$$$, representing the number of attractions.

The next $$$a$$$ lines each contain two integers $$$r$$$ and $$$c$$$ $$$(1 \leq r \leq n, 1 \leq c \leq m)$$$, the row and column of the attraction.

The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, the number of queries.

The next $$$q$$$ lines each contain two integers $$$c$$$ and $$$v$$$ $$$(1 \leq c \leq 10^5, 1 \leq v \leq a)$$$, the elevation capacity of the tourist (the height that they can never exceed) and the number of attractions they want to visit.

Output

For each query, output two integers $$$y$$$ and $$$x$$$, the row and column where the tourist should start. If there are multiple answers, output the one with the smallest $$$(y \times m + x)$$$. If an answer doesn't exist, output "-1 -1"

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

In the fifth query, starting from $$$(1, 12)$$$ allows you to visit attractions located at $$$(1, 12)$$$ and $$$(2, 12)$$$.

Credit: RandomChicken