Problem Description

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.

Input Format

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 Format

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$).

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

Hint

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<j \le N$), $X_i \ne X_j$.
• For each integer $i$ ($1 \le i \le N$), $1 \le S_i \le N$.

Subtasks

1. ($20$ points) $N \le 3\,000$.
2. ($14$ points) $K_1,K_2 \le 10$.
3. ($25$ points) For each integer $i$ ($1 \le i \le N$), $X_i \le N$ and $S_i \le 2$.
4. ($21$ points) $S_1=S_2=\cdots=S_N=1$.
5. ($10$ points) For each integer $i$ ($1 \le i \le N$), $S_i \le 2$.
6. ($10$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5