Lisa loves playing with the sequences of integers. When she gets a new integer sequence ai of length n, she starts looking for all monotone subsequences. A monotone subsequence [l, r] is defined by two indices l and r (1 ≤ l < r ≤ n) such that ∀i = l, l + 1, ..., r - 1: ai ≥ ai+1 or ∀i = l, l + 1, ..., r - 1: ai ≥ ai+1.

Lisa considers a sequence ai 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 bi 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 bi, so that Lisa does not get bored playing with it. However, Lucas is lazy and wants to change as few elements of the sequence bi as possible. Your task is to help Lucas find the required changes.

Input

The first line contains two integers n and k (3 ≤ k ≤ n ≤ 106) - the length of the sequence and Lisa’s boredom threshold. The second line contains n integers bi (1 ≤ bi ≤ 99999) - the original sequence that Lucas has.

Output

On the first line output an integer m - the minimal number of elements in bi that needs to be changed to make the sequence not boring for Lisa. On the second line output n integers ai (0 ≤ ai ≤ 105), so that the sequence of integers ai is not boring for Lisa and is different from the original sequence bi in exactly m positions.