Lisa loves playing with the sequences of integers. When she gets a new integer sequence (a_i) of length (n), she starts looking for all monotone subsequences. A monotone subsequence (l, r) is defined by two indices (l) and (r) ((1 \le l < r \le n)) such that (\forall i = l, l+1, \ldots, r-1: a_i \le a_{i+1}) or (\forall i = l, l+1, \ldots, r-1: a_i \ge a_{i+1}). Lisa considers a sequence (a_i) to be boring if there is a monotone subsequence (l, r) that is as long as her boredom threshold (k), that is when (r - l + 1 = k). Lucas has a sequence (b_i) that he wants to present to Lisa, but the sequence might be boring for Lisa. So, he wants to change some elements of his sequence (b_i), so that Lisa does not get bored playing with it. However, Lucas is lazy and wants to change as few elements of the sequence (b_i) as possible. Your task is to help Lucas find the required changes. The first line of the input contains two integers (n) and (k) ((3 \le k \le n \le 10^6)) — the length of the sequence and Lisa's boredom threshold. The second line contains (n) integers (b_i) ((1 \le b_i \le 99\,999)) — the original sequence that Lucas has. On the first line output an integer (m) — the minimal number of elements in (b_i) that needs to be changed to make the sequence not boring for Lisa. On the second line output (n) integers (a_i) ((0 \le a_i \le 100\,000)), so that the sequence of integers (a_i) is not boring for Lisa and is different from the original sequence (b_i) in exactly (m) positions.