Little Y has arrived in a new city for a trip. She discovers that the city's layout is grid-like, consisting of $n$ roads running from east to west and $m$ roads running from south to north. These roads intersect to form $n \times m$ intersections $(i, j)$ ($1 \le i \le n, 1 \le j \le m$).

She finds that different road segments have different conditions, so it takes different amounts of time to travel between different intersections. Through investigation, she finds that the time required to travel from intersection $(i, j)$ to intersection $(i, j+1)$ is $r_{i,j}$, and the time required to travel from intersection $(i, j)$ to intersection $(i+1, j)$ is $c_{i,j}$. Note that the roads are bidirectional, meaning the time required to travel from intersection $(i, j+1)$ to intersection $(i, j)$ is also $r_{i,j}$.

Little Y has $q$ queries, and she wants to know the minimum time required to travel from intersection $(x_1, y_1)$ to intersection $(x_2, y_2)$.

Input

The first line contains two positive integers $n, m$, representing the size of the city.

The next $n$ lines each contain $m-1$ integers, where the $j$-th integer in the $i$-th line represents the time $r_{i,j}$ to travel between adjacent intersections.

The next $n-1$ lines each contain $m$ integers, where the $j$-th integer in the $i$-th line represents the time $c_{i,j}$ to travel between adjacent intersections.

The next line contains one positive integer $q$, representing the number of queries.

The next $q$ lines each contain four positive integers $x_1, y_1, x_2, y_2$, representing the positions of two intersections.

Output

Output $q$ lines, each containing one integer representing the minimum time required to travel between the two intersections.

Data Scale and Convention

For all test data, the time between adjacent intersections does not exceed $10^4$, i.e., $1 \le r_{i,j}, c_{i,j} \le 10^4$.

The test cases satisfy the following conditions:

Examples

Input 1

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

Output 1

6
7

Input 2

2 3
558 163
102 2000
461 1732 561
2
2 1 2 3
1 2 2 2

Output 2

1743
1121