$N$ Schüler haben an einer Prüfung mit den Fächern Mathematik und Informatik teilgenommen. Der $i$-te Schüler ($1 \le i \le N$) hat $S_i$ Punkte in Mathematik und $T_i$ Punkte in Informatik erzielt. Professor T und Professor I werden anhand der Punktzahlen entscheiden, ob jeder Schüler die Prüfung besteht oder nicht.

• Professor T hält beide Fächer für wichtig. Er möchte Schüler bestehen lassen, die mindestens $A$ Punkte in Mathematik und $B$ Punkte in Informatik erzielt haben.
• Professor I hält nur die Gesamtpunktzahl für wichtig. Er möchte Schüler bestehen lassen, die insgesamt mindestens $C$ Punkte erzielt haben.
• Nur Schüler, die beide Professoren bestehen lassen möchten, können die Prüfung bestehen.

Du kennst diese Kriterien, also die Werte von $A$, $B$ und $C$, nicht. Stattdessen sind $Q$ Tripel ganzer Zahlen $(X_j, Y_j, Z_j)$ ($1 \le j \le Q$) gegeben. Du möchtest wissen, wie viele Schüler die Prüfung bestehen, wenn $A = X_j$, $B = Y_j$ und $C = Z_j$ gelten.

Schreibe ein Programm, das anhand der Anzahl der Schüler, der Punktzahlen jedes Schülers und einiger Kriterien für jedes Kriterium die Anzahl der Schüler berechnet, die die Prüfung bestehen.

Eingabe

Lies die folgenden Daten von der Standardeingabe. Alle Eingabewerte sind ganze Zahlen.

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

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Die $j$-te Zeile ($1 \le j \le Q$) soll die Anzahl der Schüler enthalten, die die Prüfung bestehen, wenn $A = X_j$, $B = Y_j$ und $C = Z_j$ gelten.

Beschränkungen

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

Teilaufgaben

1. (2 Punkte) $N \le 3\,000$, $Q \le 3\,000$.
2. (20 Punkte) $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 Punkte) $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 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 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

Ausgabe 1

2
4
1
1

Hinweis

• Wenn $A = 20$, $B = 50$ und $C = 120$ gelten, haben nur der 1. und der 2. Schüler mindestens 20 Punkte in Mathematik, mindestens 50 Punkte in Informatik und insgesamt mindestens 120 Punkte erzielt. Daher bestehen 2 Schüler die Prüfung.
• Wenn $A = 10$, $B = 10$ und $C = 100$ gelten, haben nur der 1., der 2., der 4. und der 5. Schüler mindestens 10 Punkte in Mathematik, mindestens 10 Punkte in Informatik und insgesamt mindestens 100 Punkte erzielt. Daher bestehen 4 Schüler die Prüfung.
• Wenn $A = 60$, $B = 60$ und $C = 80$ gelten, hat nur der 2. Schüler mindestens 60 Punkte in Mathematik, mindestens 60 Punkte in Informatik und insgesamt mindestens 80 Punkte erzielt. Daher besteht 1 Schüler die Prüfung.
• Wenn $A = 0$, $B = 100$ und $C = 100$ gelten, hat nur der 1. Schüler mindestens 0 Punkte in Mathematik, mindestens 100 Punkte in Informatik und insgesamt mindestens 100 Punkte erzielt. Daher besteht 1 Schüler die Prüfung.

Eingabe 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

Ausgabe 2

1
3
5
8
8
3
3
3
5
6