RCPC Simulare 2023 day 2 | D. Edenland

Alice and Bob go to edenland. Edenland is a famous adventure park where people can play various games which take place inside of a forest.

At edenland, you have numerous tracks, each consisting of several games. We will only focus on one track. This track consists of $n$ games, separated by platforms. Alice takes $a_i$ time to finish the $i^{th}$ game, while Bob takes $b_i$ time. We consider that it takes no time to pass a platform. Alice goes on the track first, followed by Bob.

However, at edenland there is a special rule: you can't overtake the person in front of you, that is, if you start behind someone, you will always be behind that person. To complete a track, you first start by playing the first game, then the second, and so on. As Bob will always be behind Alice, this rule will not change, and Alice will start the track before Bob.

There is another very important rule at edenland: no two people can play the same game at the same time, as it is not safe. Thus, if Bob is on the platform before the $i^{th}$ game, he will wait on that platform until Alice has finished the $i^{th}$ game.

Now, you are curious, for $q$ intervals $[l, r]$, what is the amount of time Bob will finish the track after Alice, if we consider only the track consisting of games $l, l+1, \dots, r$.

Input data

In the first line of input, you will read integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), representing the total number of games.

In the second lines of input, you will read $n$ integers $a_1, a_2, \dots, a_n$. ($1 \leq a_i \leq 10^9$)

In the third line of input, you will read $n$ integers $b_1, b_2, \dots, b_n$. ($1 \leq b_i \leq 10^9$)

In the fourth line of input, you will read one integer $q$, the number of queries ($1 \leq q \leq 2 \cdot 10^5$).

Every one of the next $q$ lines contains two integers $l$ and $r$. ($1 \leq l, r \leq n$)

Output data

You should output $q$ space-separated integers, the $i^{th}$ of them representing the answer for the $i^{th}$ query.

Example 1

stdin

5
4 9 4 5 3
10 5 2 9 8
3
1 5
4 4
1 2

stdout

14
9
6

Explanation

In the second query of the first test, Alice will complete game $4$ in $5$ seconds, then Bob will start it and complete it $9$ seconds later.

In the third query of the first test, Bob will start the first game when Alice finishes it. Alice will finish the second game $9$ seconds later, while Bob will finish the first game $10$ seconds later. Then, Bob will finish the second game another $5$ seconds later, so he will end $6$ seconds later than Alice.

The explanation for the rest of the examples is truly remarkable, but we consider the explanations for the second and third queries of the first test sufficient.

Example 2

stdin

8
9 10 5 10 1 7 8 10
6 3 7 4 3 1 2 9
5
6 8
3 4
2 7
4 7
1 3

stdout

9
4
2
2
7