P17137 [KOI 2026 #1] 朋友

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$）。

### 限制条件 - 输入中给出的所有数均为整数。 - $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