C. Hard Process

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a with n elements. Each element of a is either 0 or 1.

Let's denote the length of the longest subsegment of consecutive elements in a, consisting of only numbers one, as f(a). You can change no more than k zeroes to ones to maximize f(a).

Input

The first line contains two integers n and k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ n) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 1) — the elements of a.

Output

On the first line print a non-negative integer z — the maximal value of f(a) after no more than k changes of zeroes to ones.

On the second line print n integers aj — the elements of the array a after the changes.

If there are multiple answers, you can print any one of them.

Examples

input

7 1 1 0 0 1 1 0 1

output

4 1 0 0 1 1 1 1

input

10 2 1 0 0 1 0 1 0 1 0 1

output

5 1 0 0 1 1 1 1 1 0 1

记录0出现的位置，随便写几组数据可以发现要判断起始点是否为0的情况。

若起始点为0，则要判断sum[r]-sum[l]+1<=k；否则要判断sum[r]-sum[l]<=k。然后再判断一下k是否为0即可

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include