uCoder | 1357 | Nível: 5 | Tempo Limite: 3

Linearville

Adaptado por None

Competição: Maratona de Programação da SBC 2017 - Fase Nacional

The city of Linearville has N parallel two-way streets going in the West-East direction and N parallel two-way streets going in the South-North direction, making up a

grid with (N − 1) × (N − 1) blocks. The distance between two consecutive parallel streets is either 1 or 5. The Linearville Transit Authority is conducting an experiment and now requires all cars to always follow a path that alternates direction between W-E and S-N at

every crossing, meaning they must turn either left or right when reaching a crossing. The LTA is developing a new navigation app and needs your help to write a program to compute the lengths of shortest alternating paths between many pairs of start and target crossings. The alternating path in the figure, as an example for N = 10, is clearly not a shortest alternating path. But beware! Linearville may be huge.

## Entrada

The first line contains an integer N (2 ≤ N ≤ 10^{5}) representing the number of streets in each direction. For each direction, the streets are identified by distinct integers from 1 to N starting at the S-W corner of the city. The second line contains N − 1 integers D_{1} , D_{2} , . . . , D_{N −1} (D_{i} ∈ {1, 5} for i = 1, 2, . . . , N − 1) indicating the distances between consecutive streets going S-N (that is, D_{i} is the distance between street i and street i + 1). The third line contains N − 1 integers E_{1}, E_{2} , . . . , E_{N −1} (E i ∈ {1, 5} for i = 1, 2, . . . , N − 1) indicating the distances between consecutive streets going W-E (that is, E_{i} is the distance between street i and street i + 1). The fourth line contains an integer Q (1 ≤ Q ≤ 10^{5}) representing the number of shortest path queries. Each of the next Q lines describes a query with four integers A_{X} , A_{Y} , B_{X} and B _{Y} (1 ≤ A_{X} , A_{Y} , B_{X} , B_{Y} ≤ N ), indicating that the start crossing is (A_{X} , A_{Y} ) and the target crossing is (B_{X} , B_{Y} ); the values A_{X} and B_{X} are streets going S-N while the values A_{Y} and B_{Y} are streets going W-E. There are no repeated queries.

## Saída

Output Q lines, each line with an integer indicating the length of a shortest alternating path for the corresponding query of the input.

Exemplo de Entrada | Exemplo de Saída |
---|---|

5 |
23 |

10 |
46 |