$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