Problem Description

In KOI Village, there is a straight road. There are a total of $N$ houses on the road. $N$ students numbered from $1$ to $N$ live in these houses, with exactly one student in each house. For an integer $i$ ($1 \le i \le N$), the coordinate of the house where student $i$ lives is $i$. That is, the coordinate of student $1$’s house is $1$, and the coordinate of student $N$’s house is $N$.

There are two schools in KOI Village, called School $1$ and School $2$. Each student attends exactly one of these two schools.

For students $i$ and $j$ ($i \ne j$), if at least one of the following conditions holds, then the two students are said to be neighbors 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 different houses is defined as the larger coordinate minus the smaller coordinate. For example, the distance between the house where student $3$ lives and the house where student $5$ lives is $5-3=2$.

Write a program to compute, for each student, the number of students who are neighbors with them. Note that a student is not considered their own neighbor.

Input Format

The first line contains three integers $N$, $K_1$, and $K_2$, separated by spaces.

The second line contains $N$ integers $S_1,S_2,\ldots,S_N$, separated by spaces. Here, $S_i$ is the index of the school that student $i$ attends ($1 \le i \le N$).

Output Format

Output one line containing $N$ integers separated by spaces. The $i$-th integer is the number of students who are neighbors with student $i$ ($1 \le i \le N$).

5 1 2
1 1 1 2 2

1 3 3 3 2

5 1 1
1 1 1 2 2

1 2 2 2 1

7 3 1
1 1 1 1 1 1 1

3 4 5 6 5 4 3

Hint

Constraints

• All numbers in the input are integers.
• $2 \le N \le 3\,000$.
• $1 \le K_1,K_2 \le N-1$.
• For each integer $i$ ($1 \le i \le N$), $1 \le S_i \le 2$.

Subtasks

Translated by ChatGPT-5.6.

Translated by ChatGPT 5