Problem Description

There are $N$ students who will stand on a number line. On the number line, a larger value means a position further to the right.

The students stand from left to right in order of their indices from $1$ to $N$, and all positions must be integers.

Let the position of student $i$ ($1 \le i \le N$) be $B_i$. The positions must satisfy the following conditions:

• For each integer $i$ ($1 \le i \le N$), student $i$ cannot stand to the right of position $A_i$. That is, $B_i \le A_i$ must hold.
• Any two adjacent students must be at least $K$ apart. That is, for each integer $i$ ($1 \le i \le N-1$), $B_{i+1} - B_i \ge K$ must hold.

When $K = 0$, multiple students may stand at the same position.

The students want to make the position $B_1$ of student $1$ as large as possible.

Find a standing plan $[B_1, B_2, \cdots, B_N]$ that satisfies all conditions and maximizes the value of $B_1$. If multiple plans exist, output any one of them.

It can be proven that at least one valid standing plan exists.

Input Format

The first line contains two integers $N$ and $K$ separated by spaces.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces.

Output Format

Output $N$ integers $B_1, B_2, \cdots, B_N$ separated by spaces on the first line. The standing plan $[B_1, B_2, \cdots, B_N]$ must satisfy all conditions in the statement, and the value of $B_1$ must be maximized.

If multiple valid outputs exist, any one of them will be accepted.

5 2
1 4 10 9 13

1 4 6 9 12

4 0
5 2 7 3

2 2 3 3

4 3
2 1 5 9

-2 1 5 8

Hint

Constraints

• All given numbers are integers.
• $1 \le N \le 100$.
• $0 \le K \le 10$.
• For each integer $i$ ($1 \le i \le N$), $1 \le A_i \le 100$.

Subtasks

1. ($25$ points) For each integer $i$ ($1 \le i \le N-1$), $A_{i+1} - A_i \ge K$.
2. ($35$ points) $K = 0$.
3. ($30$ points) Among all standing plans that satisfy the conditions, there exists a plan with $0 \le B_1 \le 100$.
4. ($10$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5