Grid City Shortest Path

Little Y is traveling in a new city whose layout forms a grid. The city has \(n\) east–west roads and \(m\) north–south roads. These roads intersect to form \(n\times m\) intersections \((i,j)\) for \(1\leq i\leq n\) and \(1\leq j\leq m\). The travel time between intersections varies: going from intersection \((i,j)\) to \((i,j+1)\) takes time \(r(i,j)\), and going from \((i,j)\) to \((i+1,j)\) takes time \(c(i,j)\). Since the roads are bidirectional, the same time cost applies in the reverse direction.

You are given \(q\) queries. Each query provides two intersections \((x_1,y_1)\) and \((x_2,y_2)\), and your task is to determine the minimum travel time from the start to the destination.

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of east–west roads and north–south roads.

Then follow \(n\) lines. The \(i\)-th line contains \(m-1\) integers \(r(i,1), r(i,2), ... , r(i,m-1)\) indicating the time required to go from \((i,j)\) to \((i,j+1)\) for \(1\leq j\leq m-1\).

Next, there are \(n-1\) lines. The \(i\)-th of these lines contains \(m\) integers \(c(i,1), c(i,2), ... , c(i,m)\) indicating the time required to go from \((i,j)\) to \((i+1,j)\) for \(1\leq j\leq m\).

Then an integer \(q\) is given, followed by \(q\) lines, each containing four integers \(x_1, y_1, x_2, y_2\). These denote a query asking for the minimum time required to travel from intersection \((x_1,y_1)\) to \((x_2,y_2)\). All indices are 1-indexed.

outputFormat

For each query, output a single line with one integer: the minimum travel time between the given intersections.

sample

2 2
1
2
3 4
1
1 1 2 2

5