题干：

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

题目大意：

给定一个数组 a，含有 n 个元素。数组 a 中的每个元素要么是 0，要么是 1 。输入一个n，一个k，然后第二行是数组。

让我们假定，数组 a 中，仅由数字 1 组成的连续元素所构成的子分段，其最长的长度为 f(a)。您可以将不超过 k 个 0 更改为 1，使得 f(a) 最大化。

解题报告：

   这题做法多样，可以nlogn二分长度然后遍历。还有一种方法是o(n)尺取，但是感觉难写一点？

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream> 
#define ll long long
using namespace std;
const int MAX = 3e5 + 5;
int n,k;
int a[MAX],sum[MAX];

bool ok(int len) {
	for(int i = 1; i+len-1<=n; i++) {
		if(sum[i+len-1] - sum[i-1] >= len-k) return 1;
	}
	return 0;
}
int main()
{
	cin>>n>>k;
	for(int i = 1; i<=n; i++) scanf("%d",a+i),sum[i] = sum[i-1] + a[i];
	int l = 0,r = n;
	int mid = (l+r)/2;
	while(l<r) {
		mid = (l+r+1)/2;
		if(ok(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
	for(int i = 1; i+l-1<=n; i++) {
		if(sum[i+l-1] - sum[i-1] >= l-k) {
			for(int j = 1; j<=n; j++) {
				if(j < i || j > i+l-1) printf("%d",a[j]);
				else printf("1");
				if(j != n) putchar(' ');
			}
			return 0 ;
		}
	}
	
	return 0 ;
 }

总结：

  注意这题是二分求最大值，所以需要mid=(l+r+1)/2调节一下。最后还是l是我们需要的。