Linearville

Linearville has $N$ two way streets running west to east and $N$ two way streets running south to north. Together they form a grid of $(N-1) \times (N-1)$ blocks. The distance between two consecutive parallel streets is 1 or 5.

The Linearville Transit Authority is running an experiment and now requires every car to change direction at every crossing it passes. A car that reaches a crossing must turn left or right, so it can never drive straight through a crossing, and the segments of its path alternate between the west to east direction and the south to north direction. A path that obeys this rule is an alternating path. Each segment of a path joins two crossings that are consecutive on the same street, and the length of the path is the sum of the distances of its segments. The car has no previous move at the start crossing, so the first segment may run in either direction.

The figure shows an alternating path on a grid with $N = 10$. That path is not a shortest alternating path.

The authority is building a new navigation app. Given $Q$ pairs of a start crossing and a target crossing, write a program that computes the length of a shortest alternating path for each pair. Linearville may be huge.

The first line contains an integer $N$ ($2 \le N \le 100000$), the number of streets in each direction. In each direction the streets carry distinct numbers from $1$ to $N$, starting at the south west corner of the city.

The second line contains the integers $D_1, D_2, \dots, D_{N-1}$ ($D_i \in \{1, 5\}$), where $D_i$ is the distance between the south to north street $i$ and the south to north street $i+1$.

The third line contains the integers $E_1, E_2, \dots, E_{N-1}$ ($E_i \in \{1, 5\}$), where $E_i$ is the distance between the west to east street $i$ and the west to east street $i+1$.

The fourth line contains an integer $Q$ ($1 \le Q \le 100000$), the number of queries.

Each of the next $Q$ lines contains four integers $AX$, $AY$, $BX$, $BY$ ($1 \le AX, AY, BX, BY \le N$). The start crossing is $(AX, AY)$ and the target crossing is $(BX, BY)$. $AX$ and $BX$ are south to north streets, while $AY$ and $BY$ are west to east streets. No query appears twice.

Print $Q$ lines. Line $i$ contains one integer, the length of a shortest alternating path for query $i$. If the start crossing and the target crossing are the same, print 0.