Có $N$ học sinh tham dự một kỳ thi gồm hai phần: toán học 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. Giáo sư T và Giáo sư I sẽ dựa vào điểm số để quyết định mỗi học sinh đỗ hay trượt.

• Giáo sư T coi trọng cả hai môn; ông muốn những học sinh đạt ít nhất $A$ điểm toán và $B$ điểm tin được đỗ.
• Giáo sư I chỉ coi trọng tổng điểm; ông muốn những học sinh có tổng điểm ít nhất $C$ được đỗ.
• Chỉ những học sinh mà cả hai giáo sư đều muốn cho đỗ mới được đỗ kỳ thi.

Bạn không biết các tiêu chí này, tức là các giá trị $A$, $B$ và $C$. Thay vào đó, với $Q$ bộ ba số nguyên $(X_j, Y_j, Z_j)$ ($1 \le j \le Q$) được cho, bạn muốn biết số học sinh đỗ kỳ thi khi $A = X_j$, $B = Y_j$ và $C = Z_j$.

Hãy viết chương trình nhận vào số học sinh, điểm của từng học sinh và một số tiêu chí, rồi tính số học sinh đỗ kỳ thi theo từng tiêu chí.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn. Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

$$ \begin{array}{lll} N & Q \\ S_1 & T_1 \\ \vdots & \\ S_N & T_N \\ X_1 & Y_1 & Z_1 \\ \vdots & \\ X_Q & Y_Q & Z_Q \end{array} $$

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1 \le j \le Q$) phải chứa số học sinh đỗ kỳ thi khi $A = X_j$, $B = Y_j$ và $C = Z_j$.

Giới hạn

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $0 \le S_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le T_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le X_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $0 \le Y_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $0 \le Z_j \le 2\,000\,000\,000$ ($1 \le j \le Q$).

Nhiệm vụ con

1. (2 điểm) $N \le 3\,000$, $Q \le 3\,000$.
2. (20 điểm) $S_i \le 100\,000$, $T_i \le 100\,000$ ($1 \le i \le N$), $X_j \le 100\,000$, $Y_j \le 100\,000$, $Z_j = 0$ ($1 \le j \le Q$).
3. (21 điểm) $S_i \le 100\,000$, $T_i \le 100\,000$ ($1 \le i \le N$), $X_j \le 100\,000$, $Y_j \le 100\,000$, $Z_j \le 200\,000$ ($1 \le j \le Q$).
4. (57 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
4
1
1

Ghi chú

• Khi $A = 20$, $B = 50$ và $C = 120$, chỉ học sinh thứ 1 và thứ 2 đạt ít nhất $20$ điểm toán, ít nhất $50$ điểm tin và tổng điểm ít nhất $120$. Do đó, số học sinh đỗ kỳ thi là $2$.
• Khi $A = 10$, $B = 10$ và $C = 100$, chỉ học sinh thứ 1, thứ 2, thứ 4 và thứ 5 đạt ít nhất $10$ điểm toán, ít nhất $10$ điểm tin và tổng điểm ít nhất $100$. Do đó, số học sinh đỗ kỳ thi là $4$.
• Khi $A = 60$, $B = 60$ và $C = 80$, chỉ học sinh thứ 2 đạt ít nhất $60$ điểm toán, ít nhất $60$ điểm tin và tổng điểm ít nhất $80$. Do đó, số học sinh đỗ kỳ thi là $1$.
• Khi $A = 0$, $B = 100$ và $C = 100$, chỉ học sinh thứ 1 đạt ít nhất $0$ điểm toán, ít nhất $100$ điểm tin và tổng điểm ít nhất $100$. Do đó, số học sinh đỗ kỳ thi là $1$.

Dữ liệu vào 2

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

Dữ liệu ra 2

1
3
5
8
8
3
3
3
5
6