Description

Xiao Y came to a new city to travel. She found that the city layout is a grid: there are $n$ roads running from east to west and $m$ roads running from south to north. These roads intersect pairwise to form $n \times m$ intersections $(i,j)$, where $1 \le i \le n, 1 \le j \le m$.

She found that the conditions of different roads vary, so passing through different intersections takes different amounts of time. After investigation, she learned that 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)$. Note that the roads are bidirectional. Xiao Y has $q$ queries and wants to know the minimum time needed to travel from intersection $(x_1,y_1)$ to intersection $(x_2,y_2)$.

Input Format

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

The next $n$ lines each contain $m-1$ integers. In the $i$-th line, the $j$-th positive integer represents the time $r(i,j)$ to move between adjacent intersections.

The next $n-1$ lines each contain $m$ integers. In the $i$-th line, the $j$-th positive integer represents the time $c(i,j)$ to move between adjacent intersections.

The next line contains a single positive integer $q$, the number of Xiao Y’s queries.

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

Output Format

Output $q$ lines. Each line contains a single integer, the minimum time required to travel from one intersection to the other.

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

6
7

Hint

Constraints

• $n \times m \le 2 \times 10^4$.
• $q \le 10^5$.
• $1 \le r(i,j), c(i,j) \le 10^4$.

Translated by ChatGPT 5