AT_tkppc6_2_h Reversi Pieces

桌子上有 $N$ 个黑白棋子。现在，从左起第 $i$ 个棋子，如果 $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$ 个不同，则将该棋子翻面。 注意，所有询问互相独立，在第 $i$ 个询问中移除或翻转棋子不会影响第 $i+1$ 个及之后的询问。

输入按以下格式从标准输入给出。 > $N$ > $B_1$ $W_1$ > $B_2$ $W_2$ > $\vdots$ > $B_N$ $W_N$ > $Q$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\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$ - 所有输入均为整数 ### 样例解释 1 对于第 $1$ 个询问，选择 $i=1, j=3$，只操作一次是最优的。桌上剩下的棋子朝上的数字依次为 $4, 6, 8$。对于第 $2$ 个询问，一次操作都不进行是最优的。对于第 $3$ 个询问，无法进行任何操作。 ### 样例解释 2 原案: [Forested](https://atcoder.jp/users/Forested) 由 ChatGPT 4.1 翻译