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]~.