問題文

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

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

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

制約

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

小課題

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

入力例 1

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

出力例 1

60
0
50

案 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 の制約を満たす．

入力例 2

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

出力例 2

5
7
15

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

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

入力例 3

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

出力例 3

4303050130
2163001618
3957825141
5678671254
4247422035
861052753
4575390808
5678671254
5678671254

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