题目描述

$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$ 时，通过考试的学生人数。

编写一个程序，输入学生人数、每名学生的分数以及一些标准，计算在每组标准下通过考试的学生人数。

输入格式

从标准输入读取以下数据。输入中的所有值均为整数。

$N\ Q$

$S_1\ T_1$

$\vdots$

$S_N\ T_N$

$X_1\ Y_1\ Z_1$

$\vdots$

$X_Q\ Y_Q\ Z_Q$

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含当 $A = X_j$、$B = Y_j$、$C = Z_j$ 时通过考试的学生人数。

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

2
4
1
1

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

1
3
5
8
8
3
3
3
5
6

提示

样例 1 解释

• 当 $A = 20$、$B = 50$ 且 $C = 120$ 时，只有第 1 名和第 2 名学生能在数学中至少得 20 分，在信息学中至少得 50 分，且总分至少为 120 分。因此，通过考试的学生人数为 2。
• 当 $A = 10$、$B = 10$ 且 $C = 100$ 时，只有第 1 名、第 2 名、第 4 名和第 5 名学生能在数学中至少得 10 分，在信息学中至少得 10 分，且总分至少为 100 分。因此，通过考试的学生人数为 4。
• 当 $A = 60$、$B = 60$ 且 $C = 80$ 时，只有第 2 名学生能在数学中至少得 60 分，在信息学中至少得 60 分，且总分至少为 80 分。因此，通过考试的学生人数为 1。
• 当 $A = 0$、$B = 100$ 且 $C = 100$ 时，只有第 1 名学生能在数学中至少得 0 分，在信息学中至少得 100 分，且总分至少为 100 分。因此，通过考试的学生人数为 1。

数据范围

• $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 分）无额外约束。

翻译由 Qwen3-235B 完成