Problem Description

There are $ N $ Reversi pieces on a table. Currently, the piece at the $ i $th position from the left is facing up with the black side if $ i $ is odd, and with the white side if $ i $ is even. Additionally, each piece has a number $ B_i $ on its black side and a number $ W_i $ on its white side.

You are given $ Q $ queries, and you need to answer all of them. The $ i $th query is as follows:

• Remove all pieces except those from the $ L_i $th to $ R_i $th position from the left. Then, repeat the following operation any number of times (including zero):
• Let $ r $ be the number of pieces currently on the table. Choose integers $ i $ and $ j $ such that $1 \leq i \leq j \leq r$ and the pieces at the $ i $th and $ j $th positions from the left are facing the same color. For all pieces from the $ i $th to $ j $th position, if they are facing the same color as the $ i $th piece, flip them.

What is the maximum possible sum of the numbers on the faces of the pieces on the table after performing these operations?

Note that all queries are independent, meaning that the removal or flipping of pieces in one query does not affect subsequent queries.

Input Format

The input is given from the standard input in the following format:

$ N $ $ B_1 $ $ W_1 $ $\vdots$ $ B_N $ $ W_N $ $ Q $ $ L_1 $ $ R_1 $ $\vdots$ $ L_Q $ $ R_Q $

Output Format

Output $ Q $ lines. The $ i $th line should contain the answer to the $ i $th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

18
10
5

Sample Input #2

4
17 59
59 91
78 71
24 19
3
1 3
2 4
2 3

Sample Output #2

186
188
169

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq B_i \leq 10^9$
• $1 \leq W_i \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq L_i \leq R_i \leq N$
• All inputs are integers

Sample Explanation 1

For the first query, the optimal operation is to choose $ i = 1 $ and $ j = 3 $ once. The numbers on the faces of the remaining pieces will be $ 4, 6, 8 $ respectively. For the second query, the optimal strategy is to do no operations. For the third query, there is no possible operation to perform.

Sample Explanation 2

Original idea: Forested

见题面 Input 部分

见题面 Output 部分