問題文

チェリーちゃんはゼルコバ君からプレゼントとして長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ を貰った.

実は, チェリーちゃんが貰った数列は $1$ 日目の昼から次のように日に日に変化していく.

• $d$ 日目の昼に, $i=1,2, \dots, N$ のうち, $d \geq T_i$ かつ 第 $i$ 項目が正であるような全ての $i$ に対して, 第 $i$ 項目の値が $1$ 減る.

チェリーちゃんが数列 $A$ を貰ったのが $0$ 日目の夜だとしたとき, 次の $Q$ 個の質問 $1$, $\dots$, 質問 $Q$ に答えよ.

• 質問 $q$: $D_q$ 日目の夜時点におけるチェリーちゃんが貰った数列にある第 $L_q$ 項から第 $R_q$ 項まで (両端共に含む) の連続部分列における $(R_q-L_q+1)$ 個の項の総和は何か?

ただし, チェリーちゃんが住んでいる世界は次のように昼夜が変化していく.

• $0$ 日目夜 $\to$ $1$ 日目昼 $\to$ $1$ 日目夜 $\to$ $2$ 日目昼 $\to$ $\cdots$ $\to$ $(d-1)$ 日目夜 $\to$ $d$ 日目昼 $\to$ $d$ 日目夜 $\to$ $(d+1)$ 日目昼 $\to$ $\cdots$

制約

• $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$
• 入力はすべて整数

入力

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

出力

出力は $Q$ 行からなる. $q~(1 \leq q \leq Q)$ 行目には質問 $q$ に対する解答を整数で出力せよ.

最後に改行も忘れないこと.

サンプル

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