Problem Statement

Cherry received an integer sequence $A=(A_1, \dots, A_N)$ of length $N$ as a present from Zelkova.

In fact, the sequence Cherry received changes day by day, starting from the daytime of day $1$, as follows.

• During the daytime of day $d$, for every $i$ among $i=1,2, \dots, N$ such that $d \geq T_i$ and the $i$-th term is positive, the value of the $i$-th term decreases by $1$.

Assuming that Cherry received the sequence $A$ on the night of day $0$, answer the following $Q$ queries: Query $1$, $\dots$, Query $Q$.

• Query $q$: As of the night of day $D_q$, what is the sum of the $(R_q-L_q+1)$ terms in the contiguous subarray from the $L_q$-th term to the $R_q$-th term (both ends inclusive) of the sequence Cherry received?

Here, day and night change in the world where Cherry lives as follows.

• Night of day $0$ $\to$ daytime of day $1$ $\to$ night of day $1$ $\to$ daytime of day $2$ $\to$ $\cdots$ $\to$ night of day $(d-1)$ $\to$ daytime of day $d$ $\to$ night of day $d$ $\to$ daytime of day $(d+1)$ $\to$ $\cdots$

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq D_q \leq 2 \times 10^9$
• $1 \leq L_q \leq R_q \leq N$
• All input values are integers.

Input

$N$
$A_1$ $T_1$
$\vdots$
$A_N$ $T_N$
$Q$
$D_1$ $L_1$ $R_1$
$\vdots$
$D_Q$ $L_Q$ $R_Q$

Output

The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print the answer to Query $q$ as an integer.

Do not forget the newline at the end.

Sample

5
4 3
6 1
5 5
0 8
2 2
4
0 1 5
2 3 4
5 2 5
100 1 5

17
5
5
0

4
0 4
0 46
0 464
0 4646
3
0 1 4
1 1 4
10 1 4

0
0
0

10
314159265 358979323 
846264338 327950288
419716939 937510582
97494459 230781640
628620899 862803482
534211706 798214808
651328230 664709384
460955058 223172535
940812848 111745028
410270193 852110555
5
271828182 3 5
845904523 2 8
536028747 4 10
1352662497 1 7
757247093 6 9

1104785754
2333303020
2889059001
143326906
1388313008