JOI-kun sở hữu một cửa hàng đá quý. Có \(N\) khách muốn mua đá quý tại cửa hàng. Khách \(i\) có thể đến cửa hàng vào bất kỳ thời điểm nào từ \(L_i\) đến \(R_i\), kể cả hai đầu mút, và muốn mua \(C_i\) viên đá quý. Cửa hàng luôn có đủ hàng.

Vì bận rộn nên JOI-kun không thể mở cửa hàng liên tục. Cậu cân nhắc \(M\) phương án mở cửa. Trong phương án \(j\), cửa hàng mở liên tục từ thời điểm \(S_j-0.1\) đến \(T_j+0.1\). Khách \(i\) sẽ đến và mua \(C_i\) viên nếu tồn tại ít nhất một thời điểm thuộc cả \([L_i,R_i]\) và khoảng mở cửa; nếu không thì khách không mua. Hãy tính tổng số đá quý bán được cho từng phương án.

Dữ liệu vào

Dòng đầu chứa \(N\). \(N\) dòng tiếp theo, dòng \(i\) chứa \(L_i,R_i,C_i\). Dòng kế tiếp chứa \(M\). \(M\) dòng cuối, dòng \(j\) chứa \(S_j,T_j\).

Dữ liệu ra

In \(M\) dòng; dòng \(j\) là số đá quý bán được trong phương án \(j\).

Ràng buộc

• \(1\le N,M\le300000\).
• \(1\le L_i<R_i\le1000000\).
• \(1\le S_j\le T_j\le1000000\).
• \(1\le C_i\le10^9\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(12\) điểm: \(N,M\le1000\).
2. \(17\) điểm: \(S_j=T_j\) với mọi \(j\).
3. \(21\) điểm: \(S_j=1\) với mọi \(j\).
4. \(23\) điểm: \(S_j\le S_{j+1}\) và \(T_j\le T_{j+1}\) với mọi \(j<M\).
5. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

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

Nguồn

JOI 2025/2026 Semifinal Stage, bài Jeweler. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.