Lisa 喜欢玩整数序列。当她得到一个长度为 $n$ 的新整数序列 $a_i$ 时，她会开始寻找所有的单调子序列。单调子序列 $[l, r]$ 由两个下标 $l$ 和 $r$ ($1 \le l < r \le n$) 定义，满足 $\forall i = l, l + 1, \dots, r - 1 : a_i \le a_{i+1}$ 或 $\forall i = l, l + 1, \dots, r - 1 : a_i \ge a_{i+1}$。

如果序列 $a_i$ 中存在一个长度达到她厌倦阈值 $k$ 的单调子序列，即当 $r - l + 1 = k$ 时，Lisa 就会认为该序列是“无聊的”。

Lucas 有一个他想送给 Lisa 的序列 $b_i$，但这个序列对 Lisa 来说可能是无聊的。因此，他想修改序列 $b_i$ 中的一些元素，使得 Lisa 在玩这个序列时不会感到无聊。然而，Lucas 很懒，他希望尽可能少地修改 $b_i$ 中的元素。你的任务是帮助 Lucas 找到所需的修改方案。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($3 \le k \le n \le 10^6$)，分别表示序列的长度和 Lisa 的厌倦阈值。第二行包含 $n$ 个整数 $b_i$ ($1 \le b_i \le 99\,999$)，即 Lucas 原有的序列。

输出格式

第一行输出一个整数 $m$，表示为了使序列对 Lisa 不再无聊，需要修改的 $b_i$ 中元素的最少数量。第二行输出 $n$ 个整数 $a_i$ ($0 \le a_i \le 100\,000$)，使得整数序列 $a_i$ 对 Lisa 不再无聊，且与原序列 $b_i$ 恰好在 $m$ 个位置上不同。

样例

输入 1

5 3
1 2 3 4 5

输出 1

2
1 0 3 0 5

输入 2

6 3
1 1 1 1 1 1

输出 2

3
1 100000 0 1 0 1

输入 3

6 4
1 1 4 4 1 1

输出 3

1
1 1 4 0 1 1

输入 4

6 4
4 4 4 2 2 2

输出 4

2
4 4 0 2 0 2

输入 5

6 4
4 4 4 3 4 4

输出 5

1
4 4 100000 3 4 4

输入 6

8 4
2 1 1 3 3 1 1 2

输出 6

2
2 1 1 3 0 1 0 2

输入 7

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

输出 7

2
1 1 100000 2 2 100000 1 2 2 1

输入 8

7 5
5 4 4 3 4 4 4

输出 8

0
5 4 4 3 4 4 4

输入 9

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

输出 9

1
1 1 1 1 1 1 1 1 0 1