Shortest Travel Time in a Grid

Given a grid of intersections with roads connecting them, your task is to compute the shortest travel time between specified intersections. The grid has r rows and c columns, and travel times on the roads are provided by two matrices: one for east-west roads and one for north-south roads.

For any intersection represented as \((i, j)\), the cost to move right (from \((i, j)\) to \((i, j+1)\)) is given by the east-west matrix and the cost to move down (from \((i, j)\) to \((i+1, j)\)) is given by the north-south matrix. Similarly, left and upward moves use the corresponding adjacent road values.

Use Dijkstra's algorithm to compute the minimum travel time between the start intersection \((r_1, c_1)\) and the destination intersection \((r_2, c_2)\) for each query.

inputFormat

The input is given as follows:

 r c
 (Next r lines): Each line contains c integers representing the east-west roads.
 (Next r-1 lines if r > 1; otherwise, 1 line): Each line contains c integers representing the north-south roads.
 q
 (Next q lines): Each line contains four integers: r1 c1 r2 c2

Note: Even if \(r = 1\), one line for north-south roads is provided.

outputFormat

For each query, output the shortest travel time on a separate line.

## sample

3 3
1 2 0
3 1 0
2 1 0
4 2 3
2 3 2
2
1 1 3 3
2 2 3 1

6
5

</p>