You are given a permutation $p_1,p_2,\dots ,p_N$ of $1,2,\dots ,N$. In one operation, you may select any subsequence of $p$ consisting of no more than $K$ elements and sort the elements of that subsequence in increasing order. However, each element of $p$ may only be selected in at most one operation. Given these conditions, determine the lexicographically smallest permutation possible after performing some number of operations.

Constraints

$1\le K\le N\le {10}^6$

$p_1,p_2,\dots ,p_N$ is a permutation of $1,2,\dots ,N$.

Subtask 1 [40%]

$1\le K\le N\le 5\times {10}^3$

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $K$.

The second line contains $N$ integers $p_1,p_2,\dots ,p_N$.

Output Specification

Output $N$ integers on a single line, representing the lexicographically smallest permutation possible after performing some number of operations.

Sample Input

8 3
4 7 6 2 8 3 1 5

Sample Output

1 2 3 5 4 6 8 7

Explanation

In the first operation, we may select the subsequence consisting of the elements at indices $3$ and $6$. Sorting this subsequence yields $p=[4,7,3,2,8,6,1,5]$.

Then, we may select the subsequence consisting of the elements at indices $1$, $5$, and $7$. Sorting this subsequence yields $p=[1,7,3,2,4,6,8,5]$.

Finally, we may select the subsequence consisting of the elements at indices $2$, $4$, and $8$. Sorting this subsequence yields $p=[1,2,3,5,4,6,8,7]$.