$N$ uczniów przystąpiło do egzaminu składającego się z części matematycznej i informatycznej. Uczeń o numerze $i$ ($1 \le i \le N$) zdobył $S_i$ punktów z matematyki i $T_i$ punktów z informatyki. Profesor T i Profesor I zamierzają na podstawie tych wyników zdecydować, czy każdy z uczniów zda egzamin.

• Profesor T uważa oba przedmioty za ważne; chce, aby zdali uczniowie, którzy zdobyli co najmniej $A$ punktów z matematyki i $B$ punktów z informatyki.
• Profesor I uważa za ważny jedynie łączny wynik; chce, aby zdali uczniowie, którzy zdobyli łącznie co najmniej $C$ punktów.
• Egzamin mogą zdać tylko uczniowie, których chcą przepuścić obaj profesorowie.

Nie znasz tych kryteriów: wartości $A$, $B$ i $C$. Zamiast tego otrzymujesz $Q$ trójek liczb całkowitych $(X_j, Y_j, Z_j)$ ($1 \le j \le Q$) i chcesz poznać liczbę uczniów, którzy zdadzą egzamin, gdy $A = X_j$, $B = Y_j$ i $C = Z_j$.

Napisz program, który na podstawie liczby uczniów, wyników każdego ucznia i pewnych kryteriów obliczy liczbę uczniów zdających egzamin dla każdego kryterium.

Wejście

Wczytaj ze standardowego wejścia następujące dane. Wszystkie wartości na wejściu są liczbami całkowitymi.

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

Wyjście

Wypisz na standardowe wyjście $Q$ wierszy. Wiersz o numerze $j$ ($1 \le j \le Q$) powinien zawierać liczbę uczniów, którzy zdadzą egzamin, gdy $A = X_j$, $B = Y_j$ i $C = Z_j$.

Ograniczenia

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

Podzadania

1. (2 punkty) $N \le 3\,000$, $Q \le 3\,000$.
2. (20 punktów) $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 punktów) $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 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

2
4
1
1

Uwagi

• Gdy $A = 20$, $B = 50$ i $C = 120$, tylko pierwszy i drugi uczeń mają co najmniej $20$ punktów z matematyki, co najmniej $50$ punktów z informatyki i łącznie co najmniej $120$ punktów. Zatem liczba uczniów zdających egzamin wynosi $2$.
• Gdy $A = 10$, $B = 10$ i $C = 100$, tylko pierwszy, drugi, czwarty i piąty uczeń mają co najmniej $10$ punktów z matematyki, co najmniej $10$ punktów z informatyki i łącznie co najmniej $100$ punktów. Zatem liczba uczniów zdających egzamin wynosi $4$.
• Gdy $A = 60$, $B = 60$ i $C = 80$, tylko drugi uczeń ma co najmniej $60$ punktów z matematyki, co najmniej $60$ punktów z informatyki i łącznie co najmniej $80$ punktów. Zatem liczba uczniów zdających egzamin wynosi $1$.
• Gdy $A = 0$, $B = 100$ i $C = 100$, tylko pierwszy uczeń ma co najmniej $0$ punktów z matematyki, co najmniej $100$ punktów z informatyki i łącznie co najmniej $100$ punktów. Zatem liczba uczniów zdających egzamin wynosi $1$.

Wejście 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

Wyjście 2

1
3
5
8
8
3
3
3
5
6