该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

塔尖信奥开了一家宝石店。

有 $n$ 位顾客，第 $i$ 位顾客可以在时间区间 $[l_i,r_i]$ 内的任意时刻到店，并打算购买 $c_i$ 个宝石。

由于店主很忙，不能一直营业，因此设计了 $m$ 个开店方案。第 $j$ 个方案表示在时间区间 $[s_j,t_j]$ 内营业。

对于某个方案，如果顾客的到访时间区间与营业时间区间存在 交集，则该顾客会到店并购买 $c_i$ 个宝石；否则不会购买。

请你对于每个方案，求出总共能卖出的宝石数量。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $l_i,r_i,c_i$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $s_j,t_j$。

输出格式

输出 $m$ 行，每行一个整数表示对应方案的答案。

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

60
0
50

样例 1 解释

• 方案 $1$：区间 $[4,6]$，三个顾客均可到访，总和为 $60$。（该区间和三个顾客的到访时间均有交集，例如顾客 $1$ 的交集为 $[6,6]$）
• 方案 $2$：区间 $[1,2]$，没有顾客到访，总和为 $0$。
• 方案 $3$：区间 $[6,8]$，顾客 $2$ 和 $3$ 到访，总和为 $50$。（由于顾客 $1$ 的到访时间为 $[3,4]$ 因此不存在交集，所以不会购买）

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

提示

数据范围

对于 $100$ 的数据：

• $1 \le n,m \le 3\times10^5$
• $1 \le l_i < r_i \le 10^6$
• $1 \le c_i \le 10^9$
• $1 \le s_j \le t_j \le 10^6$