AT_tkppc6_2_h Reversi Pieces

[problemUrl]: https://atcoder.jp/contests/tkppc6-2/tasks/tkppc6_2_h 机の上にリバーシの駒が $ 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 $ 番目以降の質問には影響を与えません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ B_1 $ $ W_1 $ $ \vdots $ $ B_N $ $ W_N $ $ Q $ $ L_1 $ $ R_1 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目の質問に対する答えを出力すること。

### 制約 - $ 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 $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 番目の質問では、 $ i\ =\ 1,\ j\ =\ 3 $ として $ 1 $ 度だけ操作をするのが最適です。机の上に残っている駒が向けている面に書かれた数は、順に $ 4,\ 6,\ 8 $ となります。 $ 2 $ 番目の質問では、一度も操作をしないのが最適です。 $ 3 $ 番目の質問では、そもそも操作をすることができません。 ### Sample Explanation 2 原案: \[Forested\](https://atcoder.jp/users/Forested)