In a company there are $n$ employees. The skill level of the $i$-th employee is denoted by an integer $a_i$.

The company wants to start a new project, which requires some of the $n$ employees. A project is considered balanced if the difference in skill between any two employees assigned to the project is at most $k$.

For every $i$ from $1$ to $n$, print the maximum number of employees that can be part of a balanced project which contains employee $i$.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$).

The second line of input contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the skill levels of the $n$ employees.

Output

For every $i$ from $1$ to $n$, print the maximum number of employees that can be part of a balanced project which contains employee $i$.

Example 1

input

6 2
1 2 3 4 6 9

output

3 3 3 3 2 1 

Note

For the first employee, a balanced project can contain employees $a_1$, $a_2$ and $a_3$.
For the second employee, a balanced project can contain employees $a_1$, $a_2$ and $a_3$.
For the third employee, a balanced project can contain employees $a_1$, $a_2$ and $a_3$.
For the fourth employee, a balanced project can contain employees $a_2$, $a_3$ and $a_4$.
For the fifth employee, a balanced project can contain employees $a_4$ and $a_5$.
The sixth employee can be part of a balanced project only by themself.

Example 2

input

15 78
98 190 175 67 109 139 297 175 789 162 109 87 165 243 72

output

8 6 8 7 8 8 2 8 1 8 8 7 8 5 7