問題文

机の上にリバーシの駒が N 個あります。現在、左から i 番目の駒は、 i が奇数のときは黒の面を、偶数のときは白の面を上に向けています。また、左から i 番目の駒には、黒の面に数 B_i が、白の面に数 W_i が書かれています。

質問が Q 個与えられるので、全てに答えてください。 i 番目の質問は次のようなものです。

• 左から L_i 番目から R_i 番目までの駒以外を全て机から取り除く。その後、次の操作を 0 回以上の任意の回数繰り返す。このとき、机の上に置かれている駒が向けている面に書かれた数の総和は最大でいくつになるか。
  • 現在机の上に置かれている駒の数を r とする。 1 \leq i \leq j \leq r かつ、左から i 番目の駒と左から j 番目の駒が向けている面の色が同じであるような整数 i と j を選ぶ。左から i 番目から j 番目までの駒全てについて、その駒の向けている面の色が左から i 番目と違うなら、その駒をひっくり返す。

なお、全ての質問は独立であり、 i 番目の質問で駒を取り除いたり駒をひっくり返したりしても、 i+1 番目以降の質問には影響を与えません。

制約

• 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
• 入力は全て整数

入力例 1

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

出力例 1

18
10
5

1 番目の質問では、 i = 1, j = 3 として 1 度だけ操作をするのが最適です。机の上に残っている駒が向けている面に書かれた数は、順に 4, 6, 8 となります。

2 番目の質問では、一度も操作をしないのが最適です。

3 番目の質問では、そもそも操作をすることができません。

入力例 2

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

出力例 2

186
188
169

原案: Forested