$N$ élèves ont passé un examen composé d'une épreuve de mathématiques et d'une épreuve d'informatique. Le $i$-ième élève ($1 \le i \le N$) a obtenu $S_i$ points en mathématiques et $T_i$ points en informatique. Professor T et Professor I vont décider, en fonction des notes, si chaque élève réussit ou échoue.

• Professor T considère les deux matières comme importantes ; il souhaite faire réussir les élèves ayant obtenu au moins $A$ points en mathématiques et $B$ points en informatique.
• Professor I considère que seul le total des points est important ; il souhaite faire réussir les élèves ayant obtenu au moins $C$ points au total.
• Seuls les élèves que les deux professeurs souhaitent faire réussir peuvent réussir l'examen.

Vous ne connaissez pas ces critères : les valeurs de $A$, $B$ et $C$. À la place, on vous donne $Q$ triplets d'entiers $(X_j, Y_j, Z_j)$ ($1 \le j \le Q$), et vous souhaitez connaître le nombre d'élèves qui réussissent l'examen lorsque $A = X_j$, $B = Y_j$ et $C = Z_j$.

Écrivez un programme qui, étant donnés le nombre d'élèves, les notes de chaque élève et plusieurs critères, calcule le nombre d'élèves qui réussissent l'examen pour chaque critère.

Entrée

Lisez les données suivantes sur l'entrée standard. Toutes les valeurs de l'entrée sont des entiers.

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

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $j$-ième ligne ($1 \le j \le Q$) doit contenir le nombre d'élèves qui réussissent l'examen lorsque $A = X_j$, $B = Y_j$ et $C = Z_j$.

Contraintes

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

Sous-tâches

1. (2 points) $N \le 3\,000$, $Q \le 3\,000$.
2. (20 points) $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 points) $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 points) Aucune contrainte supplémentaire.

Exemples

Entrée 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

Sortie 1

2
4
1
1

Remarque

• Lorsque $A = 20$, $B = 50$ et $C = 120$, seuls les premier et deuxième élèves ont obtenu au moins $20$ points en mathématiques, au moins $50$ points en informatique et au moins $120$ points au total. Le nombre d'élèves qui réussissent l'examen est donc $2$.
• Lorsque $A = 10$, $B = 10$ et $C = 100$, seuls les premier, deuxième, quatrième et cinquième élèves ont obtenu au moins $10$ points en mathématiques, au moins $10$ points en informatique et au moins $100$ points au total. Le nombre d'élèves qui réussissent l'examen est donc $4$.
• Lorsque $A = 60$, $B = 60$ et $C = 80$, seul le deuxième élève a obtenu au moins $60$ points en mathématiques, au moins $60$ points en informatique et au moins $80$ points au total. Le nombre d'élèves qui réussissent l'examen est donc $1$.
• Lorsque $A = 0$, $B = 100$ et $C = 100$, seul le premier élève a obtenu au moins $0$ point en mathématiques, au moins $100$ points en informatique et au moins $100$ points au total. Le nombre d'élèves qui réussissent l'examen est donc $1$.

Entrée 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

Sortie 2

1
3
5
8
8
3
3
3
5
6