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$ 颗宝石；否则，该顾客不会到店，也不会购买宝石。保证店内宝石数量充足，不会出现售罄的情况。
给定顾客信息以及开店时间方案，请编写程序，对于每个方案，求出宝石的总销售数量。
输入格式
输入从标准输入按以下格式给出：
$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$ 下宝石的总销售数量。
限制
- $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$）。
- 输入中的所有值均为整数。
子任务
- （12 分）$N \le 1\,000$，$M \le 1\,000$。
- （17 分）$S_j = T_j$（$1 \le j \le M$）。
- （21 分）$S_j = 1$（$1 \le j \le M$）。
- （23 分）$S_j \le S_{j+1}$，$T_j \le T_{j+1}$（$1 \le j < M$）。
- （27 分）无额外限制。
样例数据 1
输入
3 3 4 10 5 8 20 6 10 30 3 4 6 1 2 6 8
输出
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
输出
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
输出
4303050130 2163001618 3957825141 5678671254 4247422035 861052753 4575390808 5678671254 5678671254
该样例满足子任务 1、5 的限制。