Có \(N\) học sinh tham gia một kỳ thi gồm hai môn Toán và Tin học. Học sinh thứ \(i\) (\(1 \le i \le N\)) đạt \(S_i\) điểm Toán và \(T_i\) điểm Tin học. Giáo sư T và giáo sư I quyết định học sinh nào đỗ theo các tiêu chí sau:

• Giáo sư T coi trọng cả hai môn, nên muốn học sinh đạt ít nhất \(A\) điểm Toán và ít nhất \(B\) điểm Tin học được đỗ.
• Giáo sư I chỉ coi trọng tổng điểm, nên muốn học sinh có tổng điểm ít nhất \(C\) được đỗ.
• Một học sinh chỉ đỗ nếu cả hai giáo sư đều muốn học sinh đó được đỗ.

Bạn chưa biết các giá trị \(A,B,C\). Cho \(Q\) bộ ba số nguyên \((X_j,Y_j,Z_j)\) (\(1 \le j \le Q\)), hãy tính số học sinh đỗ khi \(A=X_j\), \(B=Y_j\) và \(C=Z_j\) cho từng bộ ba.

Dữ liệu vào

Đọc từ đầu vào chuẩn các số nguyên theo định dạng:

N Q
S_1 T_1
...
S_N T_N
X_1 Y_1 Z_1
...
X_Q Y_Q Z_Q

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(j\) chứa số học sinh đỗ theo bộ tiêu chí \((X_j,Y_j,Z_j)\).

Ràng buộc

• \(1 \le N,Q \le 100\,000\).
• \(0 \le S_i,T_i \le 10^9\) với \(1 \le i \le N\).
• \(0 \le X_j,Y_j \le 10^9\) với \(1 \le j \le Q\).
• \(0 \le Z_j \le 2\times 10^9\) với \(1 \le j \le Q\).
• Tất cả dữ liệu vào là số nguyên.

Phân nhóm

1. (2 điểm) \(N \le 3000\), \(Q \le 3000\).
2. (20 điểm) \(S_i,T_i \le 100\,000\) với mọi \(1 \le i \le N\); \(X_j,Y_j \le 100\,000\) và \(Z_j=0\) với mọi \(1 \le j \le Q\).
3. (21 điểm) \(S_i,T_i \le 100\,000\) với mọi \(1 \le i \le N\); \(X_j,Y_j \le 100\,000\) và \(Z_j \le 200\,000\) với mọi \(1 \le j \le Q\).
4. (57 điểm) Không có ràng buộc bổ sung.

Ví dụ

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

2
4
1
1

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

1
3
5
8
8
3
3
3
5
6

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.