J. Arcology
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You've recently moved to an arcology – a single megastructure city, which consists of an $$$n \times m$$$ rectangular grid of towers. The tower in the $$$i$$$-th row and the $$$j$$$-th column has height $$$h_{ij}$$$ and consists of $$$h_{ij}$$$ size $$$1 \times 1 \times 1$$$ blocks, one block at each level. But getting around in your new city has proven surprisingly challenging.

You can move in two ways:

  • you can move a single block up or down in the tower you're currently in, this move costs you $$$1$$$ stress as you're afraid of elevators;
  • you can walk to any block at the same level as your current one in any tower adjacent to your current one, this doesn't cause you any stress.

To plan your commute, you want to answer queries of the following form. For each query, suppose you start at the top block of the tower at the position $$$(i_a,j_a)$$$ and you need to get to the top block of the tower at $$$(i_b,j_b)$$$. Calculate the smallest possible stress of a such a journey.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$), the size of the arcology. Then follow $$$n$$$ lines of $$$m$$$ integers $$$h_{ij}$$$ $$$(1 \leq h_{ij} \leq 10^9)$$$, where the $$$j$$$-th integer in the $$$i$$$-th row specifies the height of the tower at the same position in grid. The next line contains a single integer, the number of queries $$$q$$$ $$$(1 \leq q \leq 5 \cdot 10^5)$$$. Then follow $$$q$$$ lines of four integers $$$i_a, j_a, i_b, j_b$$$ ($$$1 \leq i_a,i_b \leq n$$$, $$$1 \leq j_a,j_b \leq m$$$). These represent a query where you start at top block of the tower at the position $$$(i_a, j_a)$$$ and you need to get to the top block of the tower at $$$(i_b, j_b)$$$.

Output

Output $$$q$$$ lines. In the $$$i$$$-th line output a single integer, the smallest possible stress of a journey from start to finish for the $$$i$$$-th query.

Example
Input
2 3
7 4 1
5 3 9
3
1 1 2 3
2 2 1 3
2 3 2 3
Output
10
2
0