题目描述

KOI 村中有一条笔直的道路。道路上共有 $N$ 座房屋，编号为 $1$ 到 $N$ 的 $N$ 名学生分别居住在这些房屋中，每座房屋恰好住有一名学生。对于每个整数 $i$（$1 \le i \le N$），学生 $i$ 所居住房屋的坐标为 $X_i$。不存在多座房屋位于同一坐标的情况。

此外，KOI 村中共有 $N$ 所学校，编号为 $1$ 到 $N$。对于每个整数 $i$（$1 \le i \le N$），学生 $i$ 就读于学校 $S_i$。

对于学生 $i$ 和学生 $j$（$i \ne j$），如果满足下列条件中的至少一个，则称这两名学生互为朋友：

• 两名学生就读于同一所学校，并且两人所居住房屋之间的距离不超过 $K_1$。
• 两名学生就读于不同的学校，并且两人所居住房屋之间的距离不超过 $K_2$。

这里，两座房屋之间的距离定义为其坐标之差的绝对值。也就是说，学生 $i$ 与学生 $j$ 所居住房屋之间的距离为 $|X_i-X_j|$。

请编写一个程序，对每名学生计算其朋友人数。请注意，学生自己不算作自己的朋友。

输入格式

第一行输入三个整数 $N$、$K_1$、$K_2$，整数之间以空格分隔。

接下来 $N$ 行给出各名学生的信息。其中，第 $i$ 行输入两个整数 $X_i$、$S_i$，整数之间以空格分隔（$1 \le i \le N$）。

输出格式

第一行输出 $N$ 个整数，整数之间以空格分隔。其中，第 $i$ 个整数表示学生 $i$ 的朋友人数（$1 \le i \le N$）。

7 3 5
9 2
1 1
14 3
6 2
17 3
4 1
8 1

4 2 2 4 1 3 2

12 8 5
31 1
10 1
49 3
23 2
62 3
18 1
40 2
14 2
55 2
27 3
45 1
36 3

2 2 1 2 0 3 2 2 0 2 2 2

提示

限制条件

• 输入中给出的所有数均为整数。
• $2 \le N \le 500\,000$。
• $1 \le K_1,K_2 \le 10^9$。
• 对于每个整数 $i$（$1 \le i \le N$），均有 $1 \le X_i \le 10^9$。
• 对于任意整数 $i,j$（$1 \le i<j \le N$），均有 $X_i \ne X_j$。
• 对于每个整数 $i$（$1 \le i \le N$），均有 $1 \le S_i \le N$。

子任务

1. （$20$ 分）$N \le 3\,000$。
2. （$14$ 分）$K_1,K_2 \le 10$。
3. （$25$ 分）对于每个整数 $i$（$1 \le i \le N$），均有 $X_i \le N$ 且 $S_i \le 2$。
4. （$21$ 分）$S_1=S_2=\cdots=S_N=1$。
5. （$10$ 分）对于每个整数 $i$（$1 \le i \le N$），均有 $S_i \le 2$。
6. （$10$ 分）无附加限制。

翻译由 ChatGPT-5.6 完成