Given an $n \times m$ grid, where each adjacent pair of cells is connected bidirectionally, the weights of the horizontal edges are denoted as $A_{i,j}$, and the weights of the vertical edges are denoted as $B_{i,j}$.
For $q$ queries of the form $(a, b, c, d)$, you need to find the shortest path from $(a, b)$ to $(c, d)$.
### Input
- The first line contains two integers $n$ and $m$.
- The next $n$ lines each contain $m-1$ integers representing $A_{i,j}$.
- The next $n-1$ lines each contain $m$ integers representing $B_{i,j}$.
- The next line contains an integer $q$.
- The next $q$ lines each contain four integers $a, b, c, d$ representing a query.
### Output
- For each query, print the length of the shortest path.
### Constraints
- $1 \le n \times m \le 2 \times 10^4$.
- $1 \le A_{i,j}, B_{i,j} \le 10^4$.
- $1 \le q \le 10^5$.
- $1 \le a, c \le n$.
- $1 \le b, d \le m$.
### Example
Input:
```
2 2
4
6
12 8
2
2 2 1 1
2 1 1 2
```
Output:
```
12
14
```
