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·10^5, 0 ≤ k ≤ n) — the number of elements in a and the parameter k.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 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 a_{j} — 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

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

try:
    while True:
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        left = 0
        result = -1
        cur = 0
        for i in range(n):
            if not a[i]:
                if k:
                    k -= 1
                else:
                    if i - left > result:
                        res_left = left
                        res_right = i
                        result = i - left
                    while left < i and a[left]:
                        left += 1
                    left += 1

        if i + 1 - left > result:
            res_left = left
            res_right = i + 1
            result = i + 1 - left

        print(result)
        for i in range(res_left):
            print(a[i], end=' ')
        for i in range(result):
            print(end="1 ")
        for i in range(res_right, n):
            print(a[i], end=' ')
        print()

except EOFError:
    pass


n,k=map(int,input().split())
l=list(map(int,input().split()))
ki=i=s=0; po=1
for j in range(n):
  s+=(l[j]==0)
  while s>k: s-=(l[i]==0); i+=1
  if j-i>ki-po: po,ki=i,j
print(ki-po+1)
l[po:ki+1]=[1]*(ki-po+1)
print(' '.join(map(str,l)))

def main():
    n, k = list(map(int, input().split()))
    nums = input().split()

    nums.append('0')
    n += 1
    maxr = maxi = front = rear = 0
    while front < n:
        for front in range(front, n):
            if nums[front] == '0':
                if k > 0:
                    k -= 1
                else:
                    break

        r = front - rear
        if r > maxr:
            maxr = r
            maxi = rear

        if nums[rear] == '0':
            if front > rear:
                k += 1
            else:
                front += 1
        rear += 1

    nums.pop()
    nums[maxi:maxi+maxr] = ('1' for _ in range(maxr))
    print(maxr)
    print(' '.join(nums))

main()


    # 1
# 0.1
# True
# "sdf"
#
# [1,2,True] : list
# (1,2,True) : tuple
# {1, 2, 3} : set
# {3: 2, True: False} : dict
# range(10) : range

# l = (1,2,True)
# print(l[0])
# l = 3
#
# s = {1, 2, True, "asdf", 2.1}
# print(s)
# d = {3: 2, True: False}
# print(d)
#
# if not (2 == 3 or 1 == 1.0):
#     print('2 = 3')
# elif True:
#     xxxxx
# else:
#     print('else')
#
# if 3 not in [1,2]:
#     print('2 not in 1,2')
#
# while True:
#     break
#     continue
# sdfadf

# while continue break

# for x in range(10):
#     if x % 11 == 12:
#         print(x)
#         break
# else:
#     print('nothing')

# l = []
# l.append(1)
# length = len(l)
# c = chr(96)
# print(c)

# l = ['a', 'b', 'c']
# print(l[2:3])

# s = {1, 2}
# s.add(3)
# r = {2,4,5,6}
# print(s | r)

# def f(x):
#     def mul(x, y):
#         return x * y
#     if x == 0:
#         return 1
#     else:
#         return mul(x, f(x-1))

# x = 1
# def f():
#     x = 1
# #     print(x)
# # f()
# # print(x)
#
# import os.path
# from os.path import join
#
# import numpy as np
# #import foo
# #
# class S:
#     def __init__(self, x):
#         self.x = x
#     def print_x(self):
#         self.y = 123
#         print(self.x)
#
# o = S(1)
# o.print_x()
# print(foo.x)
# print(np.array([1,2,3]))
#
# for x in ['1','2','3']:
#
#     print(join('/Users/kaoet', x, 'bar'))

# x = list(range(10))
# print(x)
# x = [i + 1 for i in x if i % 2 == 0]
# print(x)
# l = [ 1, 2,
#     1,
#     2,
# ]
#
# for x in range(10):
#     s = """
# asdfasdfas
# df
# sda
# f
# asdf
# as
# df
# asd
# f
# """
#
# print(s)



n, m = list(map(int, input().split()))

a = list(map(int, input().split()))

r = -1

ans = 0
ans_po = 0
for l in range(n):
    if l > 0:
        if a[l - 1] == 0:
            m += 1
    while (r < n - 1 and (1 - a[r + 1]) <= m):
        r += 1;
        if (a[r] == 0):
            m = m - 1
            #print(m)
    
    
    if r - l + 1 > ans:
        ans = r - l + 1
        ans_po = l


print(ans)


for i in range(ans_po, ans_po + ans):
    a[i] = 1;


print(' '.join(map(str,a)))
    
    
    
    
    




    
    






from collections import Counter
def mp():  return list(map(int,input().split()))
def lt():  return list(map(int,input().split()))
def pt(x):  print(x)
def ip():  return input()
def it():  return int(input())
def sl(x):  return [t for t in x]
def spl(x): return x.split()
def aj(liste, item): liste.append(item)
def bin(x):  return "{0:b}".format(x)
def printlist(l): print(' '.join([str(x) for x in l]))

n,k = mp()
a = lt()
c = 0
maxx = 0
j = 0
index = None
if k == 0:
    w = ''.join([str(x) for x in a])
    y = max([len(m) for m in w.split("0")])
    print(y)
    printlist(a)
    return
for i in range(n):
    if i >= 1 and a[i-1] == 0:
        c -= 1
    while j < n and c <= k:
        if a[j] == 0:
            c += 1
        j += 1
    if c > k:
        r = j-i-1
    else:
        r = j-i
    if r > maxx:
        maxx = r
        if c > k:
            index = (i,j-1)
        else:
            index = (i,j)
a[index[0]:index[1]] = [1]*(index[1]-index[0])
print(maxx)
printlist(a)


n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
i=0
j=0
Ansp=[0,0]
zcnt=0
max=0

while i<=n-1 :
    while j<n :
        if zcnt>=k and a[j]==0 :break
        j+=1
        if not a[j-1]:
            zcnt+=1
            if zcnt>k :
                j-=1
                zcnt-=1
                break
    l=j-i
    #print(i,j,zcnt)
    if l>max :
        max=l
        Ansp=[i,j]
    if not a[i] :
        zcnt-=1
    i+=1
    

for i in range(Ansp[0],Ansp[1]) :
    a[i]=1
    
print(max)
print(" ".join(map(str,a)))

n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
i=0
j=0
Ansp=[0,0]
zcnt=0
max=0

while i<=n-1 :
    while j<n :
        if zcnt>=k and a[j]==0 :break
        j+=1
        if not a[j-1] and zcnt<k:
            zcnt+=1
        elif zcnt>k : break
    l=j-i
    #print(i,j,zcnt)
    if l>max :
        max=l
        Ansp=[i,j]
    if not a[i] :
        zcnt-=1
    i+=1
    

for i in range(Ansp[0],Ansp[1]) :
    a[i]=1
    
print(max)
print(" ".join(map(str,a)))


def read_ints():
    return [int(x) for x in input().split()]


def main():
    n, k = read_ints()
    a = read_ints()

    lo = 0
    hi = 0
    count = 0
    x = -1
    y = -1
    while hi < n:
        if count < k or a[hi] != 0:
            if a[hi] == 0:
                count += 1
            if hi - lo >= y - x:
                x = lo
                y = hi
            hi += 1
        else:
            if a[lo] == 0:
                count -= 1
            lo += 1

    if x != -1:
        print(y - x + 1)
        for i in range(x, y + 1):
            a[i] = 1
        print(" ".join(map(str, a)))
    else:
        print(0)
        print(" ".join(map(str, a)))

main()


def read_ints():
    return [int(x)for x in input().split()]
def main():
    n,k = read_ints();
    a = read_ints()
    
    lo = 0
    hi = 0
    count = 0
    x = -1
    y = -1
    
    while hi<n:
        if count < k or a[hi]!=0:
            if a[hi] == 0:
                count += 1
            if hi - lo >= y - x:
                x = lo
                y = hi
            hi+=1
        else:
            if a[lo] == 0:
                count -= 1
            lo += 1
            
    if x!=-1:
        print(y-x+1)
        
        for i in range(x,y+1):
            a[i] = 1
        print(" ".join(map(str,a)))    
    else:
        print(0)
        print(" ".join(map(str,a)))
        
main()
        
              
    
                    


import random
from collections import Counter, namedtuple

Array = namedtuple('Array', ['length', 'start', 'stop'])


def get_solution(n, k, input_list):
    array = Array(0, 0, 0)

    stop = 0
    zeros = 0

    for start in range(n):
        while stop < n:
            value = input_list[stop]
            length = stop-start+1

            if value == 0:
                zeros += 1

            # print("start is {}, stop is {}, value is {}, lengt is {}, zeros is {}".format(
            #     start, stop, value, length, zeros))

            if zeros > k and value == 0:
                zeros -= 1
                break
            else:
                if array.length < length:
                    # print("this one is better")
                    array = Array(length, start, stop+1)
                stop += 1

        if input_list[start] == 0:
            zeros -= 1

        start += 1
        # while stop - start >= k:
        #     stop -= 1
        #     zeros -= 1 is input_list[stop] == 0

    return array
    # return sorted(arrays, reverse=True)


def solve(n, k, input_list):
    solution = get_solution(n, k, input_list)
    if solution:
        length, start, stop = solution
        input_list[start:stop] = [1] * (stop - start)
        print(length)
    else:
        print(0)

    print(" ".join(map(str, input_list)))


def main():
    n, k = list(map(int, input().split()))
    input_list = list(map(int, input().split()))
    solve(n, k, input_list)


def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
s = list(map(int, input().split()))

ans = 0

def get(x) :
    return 1 - x

l = 0
cnt = 0
L = n
R = 0

for i in range(n) :
    cnt += get(s[i])
    while cnt > k :
        cnt -= get(s[l])
        l += 1
    if l <= i :    
        now = i - l + 1
        if now > ans :
            ans = now
            L = l
            R = i
            
if L <= R :
    for i in range(L, R + 1) :
        s[i] = 1

print(ans)
print(' '.join(map(str,s)))


n, k = map(int, input().split())
s = list(map(int, input().split()))

ans = 0

def get(x) :
    return 1 - x

l = 0
r = -1
cnt = 0
L = n
R = 0

while l < n :
    while r + 1 < n and cnt + get(s[r + 1]) <= k : 
        cnt += get(s[r + 1])
        r += 1
        
    now = r - l + 1
    
    if now > ans :
        ans = now
        L = l
        R = r
    cnt -= get(s[l])
    l += 1

for i in range(L, R + 1) :
    s[i] = 1

print(ans)
print(" ".join(map(str, s)))

def main():
    n, k = list(map(int, input().split()))
    l, x = list(input()[::2]), k + 1
    l.append('0')
    n += 1
    for i, c in enumerate(l):
        if c == '0':
            x -= 1
            if not x:
                break
    m, j, ji = i, -1, (-1, i)
    for i in range(i + 1, n):
        if l[i] == '0':
            for j in range(j + 1, n):
                if l[j] == '0':
                    if m < i - j:
                        m, ji = i - j, (j, i)
                    break
    j, i = ji
    j += 1
    z = i - j
    l[j:i] = ['1'] * z
    if z > n:
        z = n
    del l[-1]
    print(z)
    print(' '.join(l))


def __starting_point():
    main()

__starting_point()

3
#coding=utf-8

__metaclass__ = type
__author__ = 'xdlove'

n,k = list(map(int,input().split()))
res = [int(x) for x in input().split()] 
l,r = -1,-2

L,num_0 = 0,0
for R in range(n):
    if res[R] == 0:
        num_0 += 1
    while num_0 > k:
        if r - l < R - L: #[l,r)
            l,r = L,R
        if res[L] == 0:
            num_0 -= 1
        L += 1
    if R == n - 1 and r - l < R + 1 - L:
        l,r = L,R + 1

print(r - l)
for i in range(n):
    if l <= i < r:
        res[i] = 1
    res[i] = str(res[i])
print(' '.join(res))


n = input().split()
k = int(n[-1])
n = int(n[0])
a = [int(x) for x in input().split()]
ii = 0
zero = list()
for x in a:
    if not x:
        zero.append(ii)
    ii += 1

if len(zero)-k <= 0:
    print(n)
    string = '1'
    for x in range(1, n):
        string += ' 1'
    print(string)
elif k == 0:
    string = ''
    for x in range(len(a)):
        string += str(a[x])
    o = ''
    while string.find(o+'1') != -1:
        o += '1'
    print(len(o))
    print(' '.join(str(x) for x in a))
else:
    maxof1 = 0
    for i in range(len(zero)-k+1):
        z = 1
        l1 = 0
        while zero[i]-z >= 0 and a[zero[i] - z]:
            l1 += 1
            z += 1
        z = 1
        l2 = 0
        while zero[i+k-1]+z <= n-1 and a[zero[i + k-1] + z]:
            l2 += 1
            z += 1
        x = zero[i + k-1] - zero[i] + 1 + l1 + l2
        if maxof1 < x:
            maxof1 = x
            maxn = i
    print(maxof1)
    for i in range(maxn, maxn+k):
        a[zero[i]] = 1
    string = str(a[0])
    for x in range(1, len(a)):
        string += ' '+str(a[x])
    print(string)

n,k=map(int,input().split())
l=list(map(int,input().split()))
ki=i=s=0; po=1
for j in range(n):
  s+=(l[j]==0)
  while s>k: s-=(l[i]==0); i+=1
  if j-i>ki-po: po,ki=i,j
print(ki-po+1)
l[po:ki+1]=[1]*(ki-po+1)
print(' '.join(map(str,l)))

n,k=map(int,input().split())
ara=list(map(int,input().split()))
max=0
zero=0
value=0
end=0
for i in range(0,n):
    if ara[i]==0:
        zero+=1
    if zero<=k:
        max+=1
        end=i
    else:
        if ara[value]==0 :
            zero-= 1
        value+= 1
print(max)
for i in range(end-max+1,end+1):
    ara[i]=1
print(" ".join(map(str,ara)))

n,k=list(map(int,input().split()))
ara=list(map(int,input().split()))
max=0
zero=0
value=0
end=0
for i in range(0,n):
    if ara[i]==0:
        zero+=1
    if zero<=k:
        max+=1
        end=i
    else:
        if ara[value]==0 :
            zero-= 1
        value+= 1
print(max)
for i in range(end-max+1,end+1):
    ara[i]=1
print(" ".join(map(str,ara)))


n, k = map(int, input().split())
l = list(map(int, input().split()))
cnt = i = sm = 0
pos = 1
for j in range(n):
    sm += (l[j] == 0)
    while sm > k:
        sm -= (l[i] == 0)
        i += 1
    if j - i > cnt - pos:
        pos, cnt = i, j
print(cnt - pos + 1)
l[pos: cnt + 1] = [1] * (cnt - pos + 1)
print(' '.join(map(str, l)))

mx = 0


def f(need, c, k, n):
    for i in range(n):
        if i + need - 1 >= n:
            break
        temp = c[i + need - 1]
        if i > 0:
            temp -= c[i - 1]
        if temp + k >= need:
            return (True, i)

    return (False, None)


def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))

    c = [0 for i in range(n)]

    c[0] = a[0]

    for i in range(1, n):
        c[i] = c[i - 1]
        if a[i] == 1:
            c[i] += 1

    l, r = k, n + 1

    while r - l > 100:
        m = (l + r) // 2
        if f(m, c, k, n)[0]:
            l = m
        else:
            r = m

    for i in range(r, l - 1, -1):
        res, start = f(i, c, k, n)
        if res:
            print("%d" % i)
            print((" ".join(str(x)
                           for x in a[:start] + [1] * i + a[start + i:])))
            return

def __starting_point():
    main()
    # print(gcd(100, 2))

__starting_point()

import bisect


def readline():
    return [int(x) for x in input().strip().split()]


def to_s(iterable):
    return (str(obj) for obj in iterable)


class Solver:
    def __init__(self):
        self.n = None
        self.k = None
        self.a = None
        self.sums = []

    def main(self):
        self.n, self.k = readline()
        self.a = [0] + readline()
        self.sums.append(0)
        for val in self.a[1:]:
            self.sums.append(self.sums[-1] + (val == 0))

        best_start, best_end = 0, -1
        for i in range(1, self.n + 1):
            end = bisect.bisect_right(self.sums, self.k + self.sums[i - 1], i)
            if end - i > best_end - best_start:
                best_start, best_end = i, end

        print(best_end - best_start)
        for i in range(best_start, best_end):
            self.a[i] = 1
        print(' '.join(to_s(self.a[1:])))


Solver().main()


L=list(map(int,input().split()))
n=L[0]
k=L[1]
a=list(map(int,input().split()))

nbr0=0
posi=0
taillemax=0
p=0
for i in range(len(a)):
    nbr0+=(a[i]==0)
    if nbr0>k:
        if (i-posi)>taillemax:
            
            p=posi
            taillemax=i-posi
           
        j=posi
        while 1:
            if a[j]==0:
                posi=j+1
                break
            j=j+1
        nbr0-=1
       
if i==(n-1) and (i-posi+1)>taillemax:
    p=posi
    taillemax=i-posi+1
    #print(p,posi)
    
print(taillemax)
ch=""
for i in range(len(a)):
    if i>=p and i<(p+taillemax):
        ch+="1 "
    else:
        ch+=str(a[i])+" "
print(ch)


from sys import stdin, stdout
L=list(map(int,stdin.readline().split()))
n=L[0]
k=L[1]
a=list(map(int,stdin.readline().split()))

nbr0=0
posi=0
taillemax=0
p=0
for i in range(len(a)):
    nbr0+=(a[i]==0)
    if nbr0>k:
        if (i-posi)>taillemax:
            
            p=posi
            taillemax=i-posi
           
        j=posi
        while 1:
            if a[j]==0:
                posi=j+1
                break
            j=j+1
        nbr0-=1
       
if i==(n-1) and (i-posi+1)>taillemax:
    p=posi
    taillemax=i-posi+1
    #print(p,posi)
    
print(taillemax)
ch=""
for i in range(len(a)):
    if i>=p and i<(p+taillemax):
        ch+="1 "
    else:
        ch+=str(a[i])+" "
stdout.write(ch)


from sys import stdin, stdout
L=list(map(int,stdin.readline().split()))
n=L[0]
k=L[1]
#a=list(map(int,stdin.readline().split()))
a=[int(c) for c in stdin.readline().split()]

nbr0=0
posi=0
taillemax=0
p=0
for i in range(len(a)):
    nbr0+=(a[i]==0)
    if nbr0>k:
        if (i-posi)>taillemax:
            
            p=posi
            taillemax=i-posi
           
        j=posi
        while 1:
            if a[j]==0:
                posi=j+1
                break
            j=j+1
        nbr0-=1
       
if i==(n-1) and (i-posi+1)>taillemax:
    p=posi
    taillemax=i-posi+1
    #print(p,posi)
    
print(taillemax)
ch=""
for i in range(len(a)):
    if i>=p and i<(p+taillemax):
        ch+="1 "
    else:
        ch+=str(a[i])+" "
stdout.write(ch)


from sys import stdin, stdout
L=list(map(int,stdin.readline().split()))
n=L[0]
k=L[1]
#a=list(map(int,stdin.readline().split()))
a=[int(c) for c in stdin.readline().split()]

nbr0=0
posi=0
taillemax=0
p=0
for i in range(len(a)):
    nbr0+=(a[i]==0)
    if nbr0>k:
        if (i-posi)>taillemax:
            
            p=posi
            taillemax=i-posi
           
        j=posi
        while 1:
            if a[j]==0:
                posi=j+1
                break
            j=j+1
        nbr0-=1
       
if i==(n-1) and (i-posi+1)>taillemax:
    p=posi
    taillemax=i-posi+1
    #print(p,posi)
    
print(taillemax)
ch1=""
for i in range(len(a)):
    if i>=p and i<(p+taillemax):
        ch1+="1 "
    else:
        ch1+=str(a[i])+" "
stdout.write(ch1)