Cửa hàng JOI có \(N\) mặt hàng, được đánh số từ \(1\) đến \(N\). Mỗi mặt hàng có một giá niêm yết và một loại. Mặt hàng \(i\) (\(1 \le i \le N\)) có giá niêm yết \(P_i\) yên và thuộc loại \(A_i\). Các loại được biểu diễn bằng các số nguyên từ \(1\) đến \(M\).

Cửa hàng JOI tổ chức một đợt giảm giá kéo dài \(M\) ngày. Vào ngày thứ \(j\) (\(1 \le j \le M\)), mọi mặt hàng thuộc loại \(j\) đều được bán với giá bằng một nửa giá niêm yết.

Trong đợt giảm giá, có \(Q\) khách hàng đến cửa hàng, được đánh số từ \(1\) đến \(Q\). Khách hàng \(k\) (\(1 \le k \le Q\)) đến vào ngày thứ \(T_k\) và mua mỗi mặt hàng \(L_k, L_k+1, \ldots, R_k\) một đơn vị.

Để đánh giá hiệu quả của đợt giảm giá, cửa hàng muốn biết số tiền mỗi khách hàng đã chi. Cho thông tin về các mặt hàng và khách hàng, hãy viết chương trình tính số tiền mỗi khách hàng phải trả.

Dữ liệu vào

Dòng thứ nhất chứa ba số nguyên \(N, M, Q\).

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(P_i, A_i\).

Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa ba số nguyên \(T_k, L_k, R_k\). Các giá trị trên cùng một dòng được cách nhau bởi dấu cách.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số tiền khách hàng \(k\) phải trả, không kèm đơn vị yên.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(2 \le P_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(P_i\) là số chẵn với mọi \(1 \le i \le N\).
• \(1 \le A_i \le M\) với mọi \(1 \le i \le N\).
• \(1 \le T_k \le M\) với mọi \(1 \le k \le Q\).
• \(1 \le L_k \le R_k \le N\) với mọi \(1 \le k \le Q\).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

1. (15 điểm) \(N \le 2000\), \(M \le 2000\), \(Q \le 2000\).
2. (20 điểm) \(M = 1\).
3. (12 điểm) \(M \le 10\).
4. (14 điểm) \(A_i \ne A_j\) với mọi \(1 \le i < j \le N\).
5. (22 điểm) \(P_i = 2\) với mọi \(1 \le i \le N\).
6. (17 điểm) Không có ràng buộc bổ sung.

Ví dụ

5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5

45
50
75

5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5

80
75
135

5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4

85
170
50

10 5 4
2 1
2 5
2 4
2 3
2 4
2 2
2 2
2 4
2 2
2 1
3 2 7
1 1 7
2 1 10
5 5 8

11
13
17
8

10 10 10
741703628 7
231838922 5
920286164 3
763741914 5
246151406 7
54109256 1
966457488 5
441379880 10
458514202 2
224373612 1
5 5 10
2 2 7
1 9 9
1 3 4
9 4 6
1 1 7
9 4 7
4 8 8
7 5 9
1 4 5

1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.