Byteasar 小时候很喜欢玩积木。他习惯将积木排成 $n$ 列，每列高度随机，然后按以下方式整理：Byteasar 会选择一个数字 $k$，并尝试通过移动积木，使得其中连续的 $k$ 列高度相等。此外，他总是试图以最少的移动次数达到这个目标，其中一次移动定义为：

• 在任意一列的顶部放置一块积木（Byteasar 有一个装满备用积木的大箱子，确保此操作总是可以执行），或者
• 移除任意一列顶部的积木。

然而，Byteasar 从来不确定他的移动序列是否确实是最优的，因此他请求你编写一个程序来帮助他解决这个问题。

编写一个程序，完成以下任务：

• 从标准输入读取数字 $k$ 以及积木的初始排列，
• 确定最优解（最少移动次数的序列），
• 将解输出到标准输出。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 100\,000$)，中间用空格分隔。接下来的 $n$ 行，每行包含一列的高度；第 $i+1$ 行包含一个整数 $0 \le h_i \le 1\,000\,000$，表示第 $i$ 列的高度，即该列包含的积木数量。

输出格式

输出应为最优解，即满足以下条件的积木排列：

• 包含 $k$ 个高度相等的连续列，
• 可以通过最少次数的移动从初始状态得到。

输出应包含 $n+1$ 行，每行一个整数。第一行的数字应为达到目标排列所需的最少移动次数。第 $i+1$ 行（对于 $1 \le i \le n$）应包含 $h'_i$ —— 第 $i$ 列的最终高度。如果存在多个最优解，输出其中任意一个即可。

样例

输入 1

5 3
3
9
2
3
1

输出 1

2
3
9
2
2
2