配点 : $2000$ 点

問題文

長さ $N$ の、$1 \sim N$ をちょうど $1$ つずつ含む数列 $P_1 ... P_N$ が与えられます。

あなたはこの数列に対し、以下のような操作を何度でも行えます。

• 整数 $i,j (1 \leq i < j \leq N)$ を選ぶ。
• $P_i$ と $P_j$ の値を入れ替える。
• ただしこのとき、$j - i \geq K$ かつ $|P_i - P_j| = 1$ を満たしていなければならない。

このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

制約

• $2 \leq N \leq 500,000$
• $1 \leq K \leq N-1$
• $P$ は $1, 2, ..., N$ の順列である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$P_1$ $P_2$ $...$ $P_N$

出力

問題文中の操作によって作ることのできる辞書順最小の数列を出力せよ。

4 2
4 2 3 1

2
1
4
3

以下のような手順で操作を行えば良いです。

• $4 2 3 1$
• $4 1 3 2$
• $3 1 4 2$
• $2 1 4 3$

5 1
5 4 3 2 1

1
2
3
4
5

8 3
4 5 7 8 3 1 2 6

1
2
6
7
5
3
4
8