Mahir lives in Gridland. Gridland consists of **N **rows and **M **columns where every point has a height. To go from one cell to it’s adjacent ones Mahir needs a ladder which is at least as long as the height difference. For example to go from a cell which has height **X **to a cell which has height **Y **Mahir needs a ladder at least |**X-Y**| units long. Mahir is curious, he wants to know the the shortest ladder which allows him to go from one given cell, X, to the other, Y.

3 | 2 |

4 | 5 |

From (1*,*2) to (2*,*2) via (1*,*1) and (2*,*1), 1 unit length of ladder is sufficient.

**Important Notes:**

- Mahir can only travel from a cell to it’s adjacent ones in a single step.(i.e he can go 4 directions which are left,right,bottom and up.)
- The upper leftmost cell is (1,1) and the bottom rightmost cell is (N,M).

**BONUS: **You will be given *Q *queries, asking the minimum length of the ladder that Mahir can travel from a given cell to the other one. Correctly answering the case when *Q *= 1 will give you the maximum point. If your code correctly works in the time limitation for the case when 1 *< Q <*= 10^{5}, your name will be added to the bonus list.

# 1 Input/Output Format

## 1.1 Input Format

The first line of the input file holds two integers, *N *and *M*, showing the number of rows and the number of columns respectively.

In the following N lines, heights of cells are given, M integers in every line.

In the following line, number of queries *Q *is given.

Then, the next Q lines will have 4 integers indicating two cells of a query.

## 1.2 Output Format

Print the answer for the each query, minimum length of the ladder that Mahir can travel from a cell to the other one, in a new line.

# 2 Examples

**Sample Input**- 5

1 2 3 4 5

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

1

1 1 5 3

**Sample Output**

20

**Explanation**

(1*,*1) → (1*,*2) → (1*,*3) → (2*,*3) → (3*,*3) → (4*,*3) → (5*,*3)

**Sample Input**- 5

1 2 3 4 5

100 100 23 100 100

100 100 43 100 100

100 100 63 100 100

100 100 83 100 100

2

4 2 4 4

1 1 1 5

**Sample Output**

17

1

**Explanation**

- First query,(4
*,*2) → (5*,*2) → (5*,*3) → (5*,*4) → (4*,*4) - Second query,(1
*,*1) → (1*,*2) → (1*,*3) → (1*,*4) → (1*,*5)

## Reviews

There are no reviews yet.