친구

KOI 마을에는 일직선 형태의 도로가 있다. 이 도로 위에는 $N$개의 집이 있고, $1$번부터 $N$번까지 번호가 부여된 $N$명의 학생이 한 집에 한 명씩 살고 있다. $i$ ($1 \le i \le N$)번 학생이 살고 있는 집의 좌표는 $X_i$이다. 같은 좌표에 여러 개의 집이 존재하지 않는다.

또한, KOI 마을에는 $1$번부터 $N$번까지 번호가 부여된 $N$개의 학교들이 있다. $i$ ($1 \le i \le N$)번 학생은 $S_i$번 학교에 다닌다.

$i$번 학생과 $j$번 학생에 대해 ($i \ne j$), 아래의 조건 중 적어도 하나를 만족하면, 두 학생은 서로 친구라고 한다.

• 두 학생이 서로 같은 학교에 다니고, 두 학생의 집 사이의 거리가 $K_1$ 이하이다.
• 두 학생이 서로 다른 학교에 다니고, 두 학생의 집 사이의 거리가 $K_2$ 이하이다.

여기서, 두 집 사이의 거리는 두 집의 좌표 차이의 절댓값으로 정의한다. 즉, $i$번 학생과 $j$번 학생의 집 사이의 거리는 $\left| X_i - X_j \right|$이다.

각 학생에 대해, 그 학생의 친구가 몇 명인지 계산하는 프로그램을 작성하라. 자기 자신은 자신의 친구가 아님에 유의하라.

• 주어지는 모든 수는 정수이다.
• $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점) 추가 제약 조건 없음.

첫 줄에 세 정수 $N$, $K_1$, $K_2$가 공백으로 구분되어 차례대로 주어진다.

이후 $N$개의 줄에 걸쳐 각 학생의 정보가 주어진다. 이 중 $i$번째 줄에는 두 정수 $X_i$, $S_i$가 공백으로 구분되어 차례대로 주어진다 ($1 \le i \le N$).

첫 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. 이 중 $i$번째 정수는 $i$번 학생의 친구의 수를 의미한다 ($1 \le i \le N$).