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 .
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.
For each query:
On a new line for each query, print a single integer denoting the minimum possible weight of a path between and .