$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{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} $$

פלט

כתבו $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. (2 נקודות) $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