题目描述

给定一个长度为 $N$ 的数列 $P_1\ldots P_N$，该数列是 $1\sim N$ 的一个排列。

你可以对该数列进行如下操作任意次：

• 选择整数 $i, j$，满足 $1 \leq i < j \leq N$。
• 交换 $P_i$ 和 $P_j$ 的值。
• 但必须满足 $j - i \geq K$ 且 $|P_i - P_j| = 1$。

请你求出通过上述操作能够得到的字典序最小的数列。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $P_1$ $P_2$ $...$ $P_N$

输出格式

输出通过题目中操作能够得到的字典序最小的数列。

输入输出样例 #1

输入 #1

4 2
4 2 3 1

输出 #1

2
1
4
3

输入输出样例 #2

输入 #2

5 1
5 4 3 2 1

输出 #2

1
2
3
4
5

输入输出样例 #3

输入 #3

8 3
4 5 7 8 3 1 2 6

输出 #3

1
2
6
7
5
3
4
8

说明/提示

限制条件

• $2 \leq N \leq 500,\!000$
• $1 \leq K \leq N-1$
• $P$ 是 $1, 2, ..., N$ 的一个排列。

样例解释 1

可以按如下步骤进行操作：

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

由 ChatGPT 4.1 翻译