P17137 [KOI 2026 #1] Friends

In KOI Village, there is a straight road. There are a total of $N$ houses on the road, and $N$ students numbered from $1$ to $N$ live in these houses, with exactly one student living in each house. For each integer $i$ ($1 \le i \le N$), the coordinate of the house where student $i$ lives is $X_i$. No two houses are located at the same coordinate. In addition, there are $N$ schools in KOI Village, numbered from $1$ to $N$. For each integer $i$ ($1 \le i \le N$), student $i$ attends school $S_i$. For students $i$ and $j$ ($i \ne j$), if at least one of the following conditions is satisfied, then these two students are considered friends of each other: - The two students attend the same school, and the distance between their houses is at most $K_1$. - The two students attend different schools, and the distance between their houses is at most $K_2$. Here, the distance between two houses is defined as the absolute value of the difference of their coordinates. That is, the distance between the houses of student $i$ and student $j$ is $|X_i-X_j|$. Write a program to compute, for each student, the number of their friends. Note that a student is not considered a friend of themself.

The first line contains three integers $N$, $K_1$, and $K_2$, separated by spaces. The next $N$ lines give the information of each student. In the $i$-th of these lines, two integers $X_i$ and $S_i$ are given, separated by spaces ($1 \le i \le N$).

Output $N$ integers on the first line, separated by spaces. The $i$-th integer represents the number of friends of student $i$ ($1 \le i \le N$).

### Constraints - All numbers given in the input are integers. - $2 \le N \le 500\,000$. - $1 \le K_1,K_2 \le 10^9$. - For each integer $i$ ($1 \le i \le N$), $1 \le X_i \le 10^9$. - For any integers $i,j$ ($1 \le i