19번 - 벽력일섬

오니 무리가 나란히 달리는 두 열차를 습격했다! 오니 무리가 습격한 두 열차의 정보는 다음과 같다. \begin{itemize} \item 두 열차는 각각 1번부터 $N$번까지 $N$개의 칸이 차례로 연결되어 있고, 같은 속도로 달리고 있다. \item 각 열차에서 $i (1 \le i \le N - 1)$번 열차는 $i + 1$번 열차와 서로 인접하다. \item 첫 번째 열차의 $i (1 \le i \le N)$번 열차는 두 번째 열차의 $i$번 열차와 서로 인접하다. \item 첫 번째 열차의 $i (1 \le i \le N)$번 칸에는 $a_i$명의 승객이 타고 있고, 두 번째 열차의 $i (1 \le i \le N)$번 칸에는 $b_i$명의 승객이 타고 있다. \end{itemize} 오니는 한 객차에 너무 많은 사람이 몰려 있으면 공격하기 어렵다. 반대로, 사람이 너무 적으면 습격할 가치가 없다. 따라서 오니는 살아있는 승객 수가 $lo$ 이상 $hi$ 이하인 모든 칸에 습격한다. 오니 무리는 총 $M$번 습격해온다. 매 습격마다 오니가 습격한 칸 중 살아있는 승객이 있는 칸에서는 승객이 1명씩 희생된다. 열차에 타고 있던 피돌이는 오니 무리가 습격할 때마다 벽력일섬으로 오니를 해치우려고 한다. 벽력일섬은 인접한 칸에 존재하는 오니들을 한번에 해치울 수 있는 강력한 기술이다. 즉, 어떤 칸에 있는 오니를 벽력일섬으로 해치웠다면, 그 칸과 인접한 칸에 있는 오니도 한번에 벽력일섬으로 해치울 수 있다. 하지만 오니가 습격하지 않은 칸은 해당되지 않는다. 매 습격마다 피돌이는 최소 몇 번의 벽력일섬을 써야 모든 오니를 해치울 수 있을까?

첫 번째 줄에 열차의 길이 $N(1 \le N \le 300,000)$이 주어진다. 두 번째 줄에 첫 번째 열차에 타고 있는 승객 수의 정보 $a_1$, $a_2$, ..., $a_N$이 공백으로 구분되어 주어진다. 세 번째 줄에 두 번째 열차에 타고 있는 승객 수의 정보 $b_2$, $b_2$, ..., $b_N$이 공백으로 구분되어 주어진다. 주어지는 승객 수는 모두 $0$ 이상 $300,000$ 이하의 정수이다. 네 번째 줄에 습격의 횟수 $M(1 \le M \le 300,000)$이 주어진다. 그 다음 줄부터 $M$개의 줄에 걸쳐 각 습격의 정보 $lo$, $hi$ $(0 \le lo \le hi \le 300,000)$이 공백으로 구분되어 주어진다. 습격의 정보는 시간 순서대로 주어진다.

$M$개의 줄에 걸쳐 매 습격마다 피돌이가 써야 하는 벽력일섬의 최소 횟수를 출력한다.

\\ 서브태스크 1(10점): $N \le 2000$, $M \le 2000$ 서브태스크 2(20점): 모든 습격에서 $lo = 1$, $hi = 300,000$ 서브태스크 3(30점): 모든 습격에서 $hi = 300,000$ 서브태스크 4(40점): 추가 제한 없음