背景

莉萨喜欢玩整数序列。当她得到一个长度为$n$的整数序列$a_i$时，她会寻找所有的单调子序列。一个单调子序列$[l, r]$由两个索引$l$和$r$定义（$1 \leq l < r \leq n$），满足以下条件：对于所有的$i = l, l + 1, \dots, r - 1$，要么$a_i \leq a_{i+1}$（非递减），要么$a_i \geq a_{i+1}$（非递增）。

如果存在一个长度为$k$的单调子序列$[l, r]$，即$r - l + 1 = k$，则莉萨会觉得序列$a_i$很“无聊”。

卢卡斯有一个序列$b_i$，他想展示给莉萨，但是这个序列可能会让莉萨觉得无聊。因此，他想改变序列$b_i$中的某些元素，使莉萨不会感到无聊。然而，卢卡斯很懒，他希望尽量少地修改序列$b_i$。你的任务是帮助卢卡斯找到所需的最小修改次数。

描述

输入

第一行包含两个整数$n$和$k$，分别表示序列的长度和莉萨的无聊阈值$(3 \leq k \leq n \leq 10^6)$。
第二行包含$n$个整数$b_i$ $(1 \leq b_i \leq 99999)$ —— 卢卡斯的初始序列。

输出

第一行输出一个整数$m$，表示将序列$b_i$修改为不无聊所需的最小修改次数。
第二行输出$n$个整数$a_i$ $(0 \leq a_i \leq 100000)$ —— 修改后的序列，满足不无聊的要求，并且与原始序列$b_i$有且仅有$m$个不同的位置。

示例

5 3
1 2 3 4 5

2
1 0 3 0 5

6 3
1 1 1 1 1 1

3
1 100000 0 1 0 1

6 4
1 1 4 4 1 1

1
1 1 4 0 1 1

6 4
4 4 4 2 2 2

2
4 4 0 2 0 2

6 4
4 4 4 3 4 4

1
4 4 100000 3 4 4

8 4
2 1 1 3 3 1 1 2

2
2 1 1 3 0 1 0 2

10 4
1 1 1 2 2 1 1 2 2 1

2
1 1 100000 2 2 100000 1 2 2 1

7 5
5 4 4 3 4 4 4

0
5 4 4 3 4 4 4

10 10
1 1 1 1 1 1 1 1 1 1

1
1 1 1 1 1 1 1 1 1 0