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 .