该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

此外，村庄及周边共有 $n$ 所学校，编号为 $1 \sim n$。对于每个整数 $i$（$1 \le i \le n$），学生 $i$ 就读于学校 $s_i$。

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

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

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

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

输入格式

从文件 friend.in 中读入数据。

输入的第一行包含三个正整数 $n, K_1, K_2$，相邻整数之间以单个空格分隔。

接下来 $n$ 行给出各名学生的信息。其中，第 $i$ 行包含两个正整数 $x_i, s_i$，相邻整数之间以单个空格分隔。

输出格式

输出到文件 friend.out 中。

输出一行包含 $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

样例 3 ~ 8

见选手目录下的 friend/friend3.in ~ friend8.in 与 friend/friend3.ans ~ friend8.ans。

这六组样例分别满足子任务 1 ~ 6 的限制条件。

数据范围与提示

数据范围

对于所有测试数据，保证：

• $2 \le n \le 5 \times 10^5$
• $1 \le K_1, K_2 \le 10^9$
• $1 \le x_i \le 10^9$（$1 \le i \le n$）
• $1 \le s_i \le n$（$1 \le i \le n$）
• 对于任意整数 $i,j$（$1 \le i<j \le n$），均有 $x_i \ne x_j$

子任务

本题采用捆绑测试。

• 特殊性质 A：对于每个整数 $i$（$1 \le i \le n$），均有 $x_i \le n$ 且 $s_i \le 2$。
• 特殊性质 B：保证所有的 $s_i$ 均相等（即 $s_1=s_2=\cdots=s_n=1$）。
• 特殊性质 C：对于每个整数 $i$（$1 \le i \le n$），均有 $s_i \le 2$。