$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