Lottery

JOI-kun is planning a lottery event. In this lottery event, an even number of bags will be used. Each bag initially contains some red balls and blue balls (possibly zero). Participants will keep coming to the lottery event until at least one of the bags becomes empty. Each participant draws one ball from each bag. If the total number of red and blue balls they have drawn ends up being equal, they receive one prize. Balls drawn are not returned to the bags.

As preparation, JOI-kun has prepared $N$ bags, numbered from $0$ to $N − 1$. Bag $i$ ($0 ≤ i ≤ N − 1$) contains $X_i$ red balls and $Y_i$ blue balls.

In the lottery event, some of the $N$ bags will be selected for use. There are $Q$ plans for selecting bags. In the $j$-th plan ($1 ≤ j ≤ Q$), the bags $L_j , L_{j + 1}, \dots , R_j$ are used. Here, $R_j − L_j + 1$ is even.

To prepare the prizes for the event, JOI-kun wants to know, for each plan, the maximum possible total number of prizes participants can obtain. Write a program that, given the bag contents and the plans, returns the maximum possible total number of prizes participants can obtain for each plan.

• $2 ≤ N ≤ 200\, 000$.
• $1 ≤ Q ≤ 500\, 000$.
• $0 ≤ X_i ≤ 10^9$ ($0 ≤ i ≤ N − 1$).
• $0 ≤ Y_i ≤ 10^9$ ($0 ≤ i ≤ N − 1$).
• $0 ≤ L_j < R_j ≤ N − 1$ ($1 ≤ j ≤ Q$).
• $R_j − L_j + 1$ is even ($1 ≤ j ≤ Q$).
• Given values are all integers.