شارك $N$ طالبًا في امتحان يتألف من قسمين: الرياضيات والمعلوماتية. حصل الطالب رقم $i$ ‏($1 \le i \le N$) على $S_i$ نقطة في الرياضيات و$T_i$ نقطة في المعلوماتية. سيقرر الأستاذ T والأستاذ I نجاح كل طالب أو رسوبه بناءً على درجاته.

• يعد الأستاذ T كلتا المادتين مهمتين؛ ويريد نجاح الطلاب الذين حصلوا على $A$ نقطة على الأقل في الرياضيات و$B$ نقطة على الأقل في المعلوماتية.
• يعد الأستاذ I المجموع الكلي وحده مهمًا؛ ويريد نجاح الطلاب الذين حصلوا على مجموع لا يقل عن $C$ نقطة.
• لا يمكن أن ينجح في الامتحان إلا الطلاب الذين يريد كلا الأستاذين نجاحهم.

أنت لا تعرف هذه المعايير، أي قيم $A$ و$B$ و$C$. بدلًا من ذلك، تُعطى $Q$ ثلاثيات من الأعداد الصحيحة $(X_j,Y_j,Z_j)$ ‏($1 \le j \le Q$)، وتريد معرفة عدد الطلاب الناجحين في الامتحان عندما يكون $A=X_j$ و$B=Y_j$ و$C=Z_j$.

اكتب برنامجًا يحسب عدد الطلاب الناجحين في الامتحان وفق كل معيار، بمعلومية عدد الطلاب ودرجات كل طالب وبعض المعايير.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي. جميع القيم في الإدخال أعداد صحيحة.

$$ \begin{gathered} 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{gathered} $$

الإخراج

اكتب $Q$ أسطر إلى الإخراج القياسي. يجب أن يحتوي السطر رقم $j$ ‏($1 \le j \le Q$) على عدد الطلاب الناجحين في الامتحان عندما يكون $A=X_j$ و$B=Y_j$ و$C=Z_j$.

القيود

• $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$).

المهام الفرعية

1. (نقطتان) $N \le 3\,000$، $Q \le 3\,000$.
2. (20 نقطة) $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 نقطة) $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 نقطة) لا توجد قيود إضافية.

أمثلة

الإدخال 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

الإخراج 1

2
4
1
1

ملاحظة

• عندما يكون $A=20$ و$B=50$ و$C=120$، فإن الطالبين الأول والثاني فقط يحصلان على 20 نقطة على الأقل في الرياضيات و50 نقطة على الأقل في المعلوماتية ومجموع لا يقل عن 120 نقطة. لذلك يكون عدد الطلاب الناجحين في الامتحان 2.
• عندما يكون $A=10$ و$B=10$ و$C=100$، فإن الطلاب الأول والثاني والرابع والخامس فقط يحصلون على 10 نقاط على الأقل في الرياضيات و10 نقاط على الأقل في المعلوماتية ومجموع لا يقل عن 100 نقطة. لذلك يكون عدد الطلاب الناجحين في الامتحان 4.
• عندما يكون $A=60$ و$B=60$ و$C=80$، فإن الطالب الثاني فقط يحصل على 60 نقطة على الأقل في الرياضيات و60 نقطة على الأقل في المعلوماتية ومجموع لا يقل عن 80 نقطة. لذلك يكون عدد الطلاب الناجحين في الامتحان 1.
• عندما يكون $A=0$ و$B=100$ و$C=100$، فإن الطالب الأول فقط يحصل على 0 نقطة على الأقل في الرياضيات و100 نقطة على الأقل في المعلوماتية ومجموع لا يقل عن 100 نقطة. لذلك يكون عدد الطلاب الناجحين في الامتحان 1.

الإدخال 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

الإخراج 2

1
3
5
8
8
3
3
3
5
6