Supply Station Transportation

You are given an n×m grid map. The cell in the i^th row and j^th column has a height \(h_{i,j}\) and a militarization level \(p_{i,j}\). It is guaranteed that for any two cells that are 4-connected (i.e. cells \((a,b)\) and \((c,d)\) satisfying \(|a-c|+|b-d|=1\)), the absolute difference of their heights is at most 1:

[ |h_{a,b} - h_{c,d}| \le 1 ]

You can choose some cells to build supply stations. If a supply station is built at cell \((i,j)\), its transport range is defined as the set of all cells \((x,y)\) satisfying

[ h_{i,j} - h_{x,y} + p_{i,j} \ge |i-x|+|j-y| ]

Each supply station can transfer materials arbitrarily within its transport range.

Now, given a set of supply stations (each built at some chosen cell), define the safety level of that set as the minimum height among the chosen stations, i.e. \(\min\{h_{x,y}\}\) over all built stations.

There are \(q\) queries. In each query you are given four integers \(a, b, c, d\). The query asks: if you want to transport materials from cell \((a,b)\) to cell \((c,d)\) by building some supply stations (note that you are not required to build a station exactly at \((a,b)\) or \((c,d)\); the material may be transferred indirectly through multiple stations), what is the maximum possible safety level you can achieve? If it is impossible to complete the transportation, output -1.

Note: The input data guarantees \(p_{i,j} \le 9\) for all cells.

Input and Output Formats are described below.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) — the number of rows, the number of columns, and the number of queries.

The next \(n\) lines contain \(m\) integers each. The \(j\)th integer on the \(i\)th line is \(h_{i,j}\) — the height of cell \((i, j)\).

The following \(n\) lines also contain \(m\) integers each. The \(j\)th integer on the \(i\)th of these lines is \(p_{i,j}\) — the militarization level of cell \((i, j)\).

The next \(q\) lines each contain four integers \(a\), \(b\), \(c\), \(d\), representing a query asking to transport material from cell \((a, b)\) to cell \((c, d)\). The cells are 1-indexed.

outputFormat

For each query, output a single line containing the maximum possible safety level achievable. If it is impossible to transport the material, output -1.

sample

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

4

</p>