Problem 1884: F. Difference in Skill

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