**Rescue the flood victim**
Imagine the area as a grid, where each square represents a specific location. Each square has a number indicating how long it takes to fill up with water. Once filled, water flows to its neighboring squares (directly up, down, left, or right) those haven't started filling yet. The water starts from certain border squares where dam gates are opened, and all gates are opened at the same time.
image
In the example shown, there is a 4x4 grid where the top left corner is labeled as (0,0). The dam gates are opened at the same time at three locations: (0,0), (0,3), and (2,3). For the cell at (2,0), it takes 9 units of time for water to reach there. This means that if there are any people in cell (2,0), they must be rescued within 9 units of time before the water arrives.
Input Format
The first line contains two integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000) — the number of rows and columns in the grid.
In the next n lines, there will be m positive integers. Each integer w indicates how long it takes to fill up with water (1 ≤ w ≤ 10^6).
The next line contains one integer b (1 ≤ b ≤ Total number of border cells in the grid) — the number of border squares where there is a dam gate located.
In the next each b lines, each contains two integer x and y (0 ≤ x ≤ n-1, 0 ≤ y ≤ m -1) – the coordinate of the border square where a dam gate is located.
In the next line, there will be one positive integer t (1 ≤ t ≤ 10^5) indicating the number of queries.
The next t lines each contain two integers, q_x and q_y (0 ≤ q_x ≤ n-1 and 0 ≤ q_y ≤ m-1), which represent the coordinates of a square in the grid. For each of these coordinates, you need to calculate how much time it will take for the water to reach that square.
Constraints
(1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000)
(1 ≤ w ≤ 10^6)
(1 ≤ b ≤ Total number of border cells in the grid)
(0 ≤ x ≤ n-1, 0 ≤ y ≤ m -1)
(1 ≤ t ≤ 10^5)
(0 ≤ q_x ≤ n-1 and 0 ≤ q_y ≤ m-1)
Output Format
For each of the t queries you need output one integer which indicates how much time it will take for the water to reach that square.
Sample Input 0
4 4
5 6 1 10
4 5 3 2
5 5 5 6
12 3 5 4
3
0 0
0 3
2 3
3
0 0
1 2
2 1
Sample Output 0
0
8
11