F. Difference In Skill
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Examples
Input
6 2
1 2 3 4 6 9
Output
3 3 3 3 2 1
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
Note

Explanation of the first testcase:

  • 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.