Problem Description

You are given a sequence $a_1\sim a_n$ of length $n$. Here, the rank of $a_i$ is defined as the number of elements in $a$ that are strictly greater than $a_i$, plus $1$.

Now there are some operations to modify the elements in $a$. Before all operations, you are given a constant $k$ in advance. Before each operation, $a_i$ is defined to be movable if and only if, after only adding $k$ to $a_i$ while keeping all other values unchanged, the rank of $a_i$ does not change. Otherwise, $a_i$ is not movable in this operation. Then this operation is: add $k$ to all movable numbers in the sequence.

It can be proven that after a certain number of operations, all values in $a$ will become movable, and once this state is reached for the first time, all subsequent operations will also stay in this state. In other words, no matter how many operations you perform, the number of times each value in $a$ is in the not movable state is finite.

Now you are asked: after performing this operation sufficiently many times, how many times is each value in $a$ in the not movable state.

Input Format

The first line contains two integers $n,k$.

The next line contains $n$ integers $a_1\sim a_n$, representing the initial sequence $a$.

Output Format

Output one line with $n$ integers. The $i$-th integer indicates how many times $a_i$ is in the not movable state during the operations.

3 1
1 3 4

1 1 0

6 2
1 2 5 6 7 8

4 3 3 2 1 0

8 10
1 14 5 14 19 19 8 10

5 1 4 1 0 0 3 2

Hint

Sample #1 Explanation

Initially, $a_1=1,a_2=3,a_3=4$.

After one operation, $a_1=2,a_2=3,a_3=5$. $a_2$ is not movable because if we only add $1$ to $a_2$, its rank would change from $2$ to $1$.

After two operations, $a_1=2,a_2=4,a_3=6$. $a_1$ is not movable because if we only add $1$ to $a_1$, its rank would change from $3$ to $2$.

After three operations, $a_1=3,a_2=5,a_3=7$. In this operation, all values are movable. It can be proven that no matter how many more operations you perform, the not movable state will never appear again.

Therefore, during the process, $a_1$ is not movable once, $a_2$ is not movable once, and $a_3$ is never not movable.

Constraints and Notes

For $100\%$ of the testdata, $1\le n\le2\times10^5$, $1\le k,a_i\le10^9$.

Special property A: all $a_i$ are equal.

Special property B: for any $i<n$, $a_{i+1}=a_i+k$.

Special property C: for any $i\neq j$, $a_i\neq a_j$.

Translated by ChatGPT 5