Problem Description

JOI runs a jewelry shop. There are $N$ customers who want to buy jewels, numbered from $1$ to $N$. Customer $i$ ($1 \le i \le N$) can visit the shop at any time between time $L_i$ and time $R_i$, and plans to buy $C_i$ jewels.

JOI is very busy and cannot keep the shop open all the time. Therefore, he considers $M$ possible opening-time plans. The plans are numbered from $1$ to $M$, and plan $j$ ($1 \le j \le M$) means the shop is open from time $S_j - 0.1$ to time $T_j + 0.1$. For each plan, customer $i$ ($1 \le i \le N$) will visit the shop and buy $C_i$ jewels if there exists a time when the shop is open within the time interval in which they can visit. Otherwise, if no such time exists, customer $i$ will not visit and will not buy any jewels. However, JOI’s shop has enough jewels, so it will never run out.

Given the customer information and each opening-time plan, write a program to compute, for each plan, the total number of jewels that can be sold.

Input Format

The input is given from standard input in the following 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

Output $M$ lines to standard output. On the $j$-th line ($1 \le j \le M$), output the total number of jewels that can be sold under plan $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

In plan 1, the shop is open from time $3.9$ to time $6.1$. Customer 1 can come at time $4$, customer 2 can come at time $5$, and customer 3 can come at time $6$ to buy jewels. In total, $10 + 20 + 30 = 60$ jewels are sold.

In plan 2, the shop is open from time $0.9$ to time $2.1$. No customer can visit during the opening time, so a total of $0$ jewels are sold.

In plan 3, the shop is open from time $5.9$ to time $8.1$. Customers 2 and 3 can both come at time $7$ to buy jewels. In total, $20 + 30 = 50$ jewels are sold.

This sample input satisfies the constraints for subtasks 1 and 5.

Sample Explanation 2

In plan 1, customers 1 and 3 can visit the shop to buy jewels. In total, $1 + 4 = 5$ jewels are sold.

In plan 2, customers 1, 2, and 3 can visit the shop to buy jewels. In total, $1 + 2 + 4 = 7$ jewels are sold.

In plan 3, all customers can visit the shop to buy jewels. In total, $1 + 2 + 4 + 8 = 15$ jewels are sold.

This sample input satisfies the constraints for subtasks 1, 3, 4, and 5.

Constraints

• $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$)
• All input values are integers.

Subtasks

1. (12 points) $N \le 1000,\ M \le 1000$
2. (17 points) $S_j = T_j$ ($1 \le j \le M$)
3. (21 points) $S_j = 1$ ($1 \le j \le M$)
4. (23 points) $S_j \le S_{j+1},\ T_j \le T_{j+1}$ ($1 \le j < M$)
5. (27 points) No additional constraints.

Translated by DeepSeek.

Translated by ChatGPT 5