说明

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 君店铺的顾客信息以及开店时间的各个方案，请编写一个程序，针对每个方案求出总共能卖出多少个宝石。

输入格式

输入从标准输入中以以下格式给出：

$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$

输出格式

向标准输出输出 $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

提示

样例解释 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 的数据范围。

样例解释 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 分) 无额外限制。

翻译由 DeepSeek 完成