Description

JOI 君は宝石店を経営している．宝石店には宝石を買おうとしている客が $N$ 人おり，これらの客には $1$ から $N$ までの番号が付けられている．客 $i$ ($1 \le i \le N$) は時刻 $L_i$ から時刻 $R_i$ までの間の任意の時刻に店を訪れることができ，宝石を $C_i$ 個購入しようとしている．

JOI 君は忙しいため，常に店を開けておくことができない．そこで，店を開ける時間について $M$ 個の案を考えた．案には $1$ から $M$ までの番号が付けられており，案 $j$ ($1 \le j \le M$) は，時刻 $S_j - 0.1$ から時刻 $T_j + 0.1$ までの間店を開けるというものである．それぞれの案について，客 $i$ ($1 \le i \le N$) は，自分が訪れることができる時間帯に店が開いている時刻があれば，店を訪れ宝石を $C_i$ 個購入する．逆にそうでない場合，客 $i$ は店を訪れず，宝石を購入しない．ただし，JOI 君の店には十分な数の宝石があり，宝石が売り切れることはないものとする．

JOI 君の店の客の情報と店を開けておく時間の案が与えられたとき，それぞれの案について，宝石が合計でいくつ売れるかを求めるプログラムを作成せよ．

Input Format

入力は以下の形式で標準入力から与えられる．

$N$
$L_1\ R_1\ C_1$
$L_2\ R_2\ C_2$
$\vdots$
$L_N\ R_N\ C_N$
$M$
$S_1\ T_1$
$S_2\ T_2$
$\vdots$
$S_M\ T_M$

Output Format

標準出力に $M$ 行出力せよ．$j$ 行目 ($1 \le j \le M$) には，案 $j$ において宝石が合計でいくつ売れるかを出力せよ．

3
3 4 10
5 8 20
6 10 30
3
4 6
1 2
6 8

60
0
50

4
10 90 1
40 60 2
10 20 4
80 90 8
3
1 15
1 60
1 100

5
7
15

10
55 882 861052753
104 734 331227764
492 694 240198464
481 506 377367203
131 185 327968773
124 129 970226535
92 125 133053911
356 442 758055457
21 759 730522637
259 481 948997757
9
50 287
510 735
158 431
113 768
328 894
783 881
163 692
42 862
43 752

4303050130
2163001618
3957825141
5678671254
4247422035
861052753
4575390808
5678671254
5678671254

Hint

Sample Explanation 1

案 1 では，時刻 $3.9$ から時刻 $6.1$ まで店を開ける．客 1 は時刻 $4$ に，客 2 は時刻 $5$ に，客 3 は時刻 $6$ に店で宝石を買うことができ，宝石は合計で $10 + 20 + 30 = 60$ 個売れる．

案 2 では，時刻 $0.9$ から時刻 $2.1$ まで店を開ける．どの客も店が開いている時刻に訪れることができないため，宝石は合計で $0$ 個売れる．

案 3 では，時刻 $5.9$ から時刻 $8.1$ まで店を開ける．客 2，客 3 ともに時刻 $7$ に店で宝石を買うことができ，宝石は合計で $20 + 30 = 50$ 個売れる．

この入力例は小課題 1, 5 の制約を満たす．

Sample Explanation 2

案 1 では，客 1 と客 3 が店で宝石を買うことができ，宝石は合計で $1 + 4 = 5$ 個売れる．

案 2 では，客 1，客 2，客 3 が店で宝石を買うことができ，宝石は合計で $1 + 2 + 4 = 7$ 個売れる．

案 3 では，すべての客が店で宝石を買うことができ，宝石は合計で $1 + 2 + 4 + 8 = 15$ 個売れる．

この入力例は小課題 1, 3, 4, 5 の制約を満たす．

制約

• $1 \le N \le 300\,000$．
• $1 \le L_i < R_i \le 1\,000\,000$ ($1 \le i \le N$)．
• $1 \le C_i \le 10^9$ ($1 \le i \le N$)．
• $1 \le M \le 300\,000$．
• $1 \le S_j \le T_j \le 1\,000\,000$ ($1 \le j \le M$)．
• 入力される値はすべて整数である．

小課題

1. $(12$ 点$) N \le 1000,\ M \le 1000$．
2. $(17$ 点$) S_j = T_j$ ($1 \le j \le M$)．
3. $(21$ 点$) S_j = 1$ ($1 \le j \le M$)．
4. $(23$ 点$) S_j \le S_{j+1},\ T_j \le T_{j+1}$ ($1 \le j < M$)．
5. $(27$ 点$)$追加の制約はない．