- Prepare
- Algorithms
- Graph Theory
- Find the Path

# Find the Path

# Find the Path

You are given a table, , with rows and columns. The top-left corner of the table has coordinates , and the bottom-right corner has coordinates . The cell contains integer .

A path in the table is a sequence of cells such that for each , cell and cell share a side.

The weight of the path is defined by where is the weight of the cell .

You must answer queries. In each query, you are given the coordinates of two cells, and . You must find and print the minimum possible weight of a path connecting them.

**Note:** A cell can share sides with at most other cells. A cell with coordinates shares sides with , , and .

**Input Format**

The first line contains space-separated integers, (the number of rows in ) and (the number of columns in ), respectively.

Each of subsequent lines contains space-separated integers. The integer in the line denotes the value of .

The next line contains a single integer, , denoting the number of queries.

Each of the subsequent lines describes a query in the form of space-separated integers: , , , and , respectively.

**Constraints**

For each query:

**Output Format**

On a new line for each query, print a single integer denoting the minimum possible weight of a path between and .

**Sample Input**

```
3 5
0 0 0 0 0
1 9 9 9 1
0 0 0 0 0
3
0 0 2 4
0 3 2 3
1 1 1 3
```

**Sample Output**

```
1
1
18
```

**Explanation**

The input table looks like this:

The first two queries are explained below:

In the first query, we have to find the minimum possible weight of a path connecting and . Here is one possible path:

The total weight of the path is .

- In the second query, we have to find the minimum possible weight of a path connecting and . Here is one possible path: The total weight of the path is .