리니어빌

리니어빌에는 서에서 동으로 뻗은 양방향 도로 $N$개와 남에서 북으로 뻗은 양방향 도로 $N$개가 있다. 이 도로들이 만나 $(N-1) \times (N-1)$개의 블록으로 이루어진 격자를 이룬다. 나란한 두 도로 사이의 거리는 1 또는 5이다.

리니어빌 교통국은 실험을 시작하면서, 모든 차량이 지나가는 모든 교차로에서 방향을 바꾸도록 규정했다. 교차로에 도착한 차량은 왼쪽이나 오른쪽으로 반드시 꺾어야 한다. 즉 교차로를 직진으로 통과하지 못하고, 경로를 이루는 구간의 방향은 동서 방향과 남북 방향을 번갈아 나타난다. 이 규칙을 지키는 경로를 교대 경로라고 한다. 경로의 각 구간은 같은 도로 위에서 이웃한 두 교차로를 잇고, 경로의 길이는 지나간 구간의 거리를 모두 더한 값이다. 출발 교차로에는 직전 이동이 없으므로 첫 구간은 두 방향 중 어느 쪽으로 나아가도 된다.

그림은 $N = 10$인 격자 위의 교대 경로 하나를 보여 준다. 이 경로는 최단 교대 경로가 아니다.

교통국은 새 길찾기 앱을 만들고 있다. 출발 교차로와 도착 교차로의 쌍 $Q$개가 주어질 때, 각 쌍마다 최단 교대 경로의 길이를 구하는 프로그램을 작성하시오. 리니어빌은 매우 클 수 있다.

첫째 줄에 각 방향의 도로 수 $N$ ($2 \le N \le 100000$)이 주어진다. 각 방향의 도로는 도시의 남서쪽 모서리에서 시작해 $1$부터 $N$까지 서로 다른 번호로 구분한다.

둘째 줄에 정수 $D_1, D_2, \dots, D_{N-1}$ ($D_i \in \{1, 5\}$)이 주어진다. $D_i$는 남북 방향 도로 $i$와 남북 방향 도로 $i+1$ 사이의 거리이다.

셋째 줄에 정수 $E_1, E_2, \dots, E_{N-1}$ ($E_i \in \{1, 5\}$)이 주어진다. $E_i$는 동서 방향 도로 $i$와 동서 방향 도로 $i+1$ 사이의 거리이다.

넷째 줄에 질의의 수 $Q$ ($1 \le Q \le 100000$)가 주어진다.

다음 $Q$개의 줄에는 각각 네 정수 $AX$, $AY$, $BX$, $BY$ ($1 \le AX, AY, BX, BY \le N$)가 주어진다. 출발 교차로는 $(AX, AY)$이고 도착 교차로는 $(BX, BY)$이다. $AX$와 $BX$는 남북 방향 도로의 번호, $AY$와 $BY$는 동서 방향 도로의 번호이다. 같은 질의가 두 번 주어지지 않는다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의에 대한 최단 교대 경로의 길이를 정수 하나로 출력한다. 출발 교차로와 도착 교차로가 같으면 0을 출력한다.