Problem: 1

Problem Statement

There is a bit string of length n.

When the i-th bit from the left is 1, the score is a_i points.
The number of 1s within the distance w around the i-th bit from the left (= | \\ {j \ in \\ {1, ..., n \\} ∩ \\ {iw, ..., i + w \\} | When the jth bit from the left is 1 \\} |) is odd, the score is b_i.

Find the bit string that gives the most scores.

Constraints

* 1 ≤ n ≤ 1,000
* 1 ≤ w ≤ 1,000
* 0 ≤ a_i ≤ 10 ^ 5
* 0 ≤ b_i ≤ 10 ^ 5

Input

Input follows the following format. All given numbers are integers.


n w
a_1 ... a_n
b_1 ... b_n

Output

Output the bit string that gives the most scores on one line.
If there are multiple such solutions, any of them may be output.

Examples

Input

4 1
3 1 2 7
13 8 25 9


Output

1001


Input

2 1
1 1
3 3


Output

10

Solution (in CPP):

Solution:
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int N_MAX=1000;
const int W_MAX=1000;

const int V_MAX=N_MAX+2*W_MAX+3;
const int E_MAX=2*N_MAX+2*W_MAX+2;

template<class T>
struct graph{
	int n,m,head[V_MAX],next[2*E_MAX],to[2*E_MAX];
	T capa[2*E_MAX],flow[2*E_MAX];

	void init(int N){
		n=N;
		m=0;
		rep(u,n) head[u]=-1;
	}

	void add_directed_edge(int u,int v,T ca){
		next[m]=head[u]; head[u]=m; to[m]=v; capa[m]=ca; flow[m]=0; m++;
		next[m]=head[v]; head[v]=m; to[m]=u; capa[m]= 0; flow[m]=0; m++;
	}

	void add_undirected_edge(int u,int v,T ca){
		next[m]=head[u]; head[u]=m; to[m]=v; capa[m]=ca; flow[m]=0; m++;
		next[m]=head[v]; head[v]=m; to[m]=u; capa[m]=ca; flow[m]=0; m++;
	}
};

const int INF=1<<29;

int layer[V_MAX],now[V_MAX];

template<class T>
bool make_layer(const graph<T> &G,int s,int t){
	int n=G.n;
	rep(u,n) layer[u]=(u==s?0:-1);

	int head=0,tail=0;
	static int Q[V_MAX]; Q[tail++]=s;
	while(head<tail && layer[t]==-1){
		int u=Q[head++];

		for(int e=G.head[u];e!=-1;e=G.next[e]){
			int v=G.to[e];
			T capa=G.capa[e],flow=G.flow[e];

			if(capa-flow>0 && layer[v]==-1){
				layer[v]=layer[u]+1;
				Q[tail++]=v;
			}
		}
	}

	return layer[t]!=-1;
}

template<class T>
T augment(graph<T> &G,int u,int t,T water){
	if(u==t) return water;

	for(int &e=now[u];e!=-1;e=G.next[e]){
		int v=G.to[e];
		T capa=G.capa[e],flow=G.flow[e];

		if(capa-flow>0 && layer[v]>layer[u]){
			T w=augment(G,v,t,min(water,capa-flow));
			if(w>0){
				G.flow[ e ]+=w;
				G.flow[e^1]-=w;
				return w;
			}
		}
	}
	return 0;
}

template<class T>
T Dinic(graph<T> &G,int s,int t){
	int n=G.n;
	T ans=0;
	while(make_layer(G,s,t)){
		rep(u,n) now[u]=G.head[u];
		for(T water=1;water>0;ans+=water) water=augment(G,s,t,INF);
	}
	return ans;
}

template<class T>
vector<int> minimum_cut(const graph<T> &G,int s,int t){
	int n=G.n;
	static bool vis[V_MAX];
	rep(u,n) vis[u]=false;
	vis[s]=true;

	queue<int> Q; Q.push(s);
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		for(int e=G.head[u];e!=-1;e=G.next[e]){
			int v=G.to[e];
			T capa=G.capa[e],flow=G.flow[e];
			if(!vis[v] && capa-flow>0) vis[v]=true, Q.push(v);
		}
	}

	vector<int> res;
	rep(u,n) if(vis[u]) res.push_back(u);
	return res;
}

int main(){
	int n,w; scanf("%d%d",&n,&w);
	int a[N_MAX],b[N_MAX];
	rep(i,n) scanf("%d",a+i);
	rep(i,n) scanf("%d",b+i);

	int ans=INF;
	vector<int> seq;

	static graph<int> G;
	int s=n+w,t=n+w+1,OFSET=w+1;
	rep(parity,2){
		G.init(n+2*w+3);
		rep(i,n){
			G.add_undirected_edge( i-1 +OFSET, i +OFSET,a[i]);
			G.add_undirected_edge(i-w-1+OFSET,i+w+OFSET,b[i]);
		}
		for(int i=-w-1;i<=-1;i++){
			if(i%2==0) G.add_directed_edge(s+OFSET,i+OFSET,INF);
			else       G.add_directed_edge(i+OFSET,t+OFSET,INF);
		}

		int par=(parity==n%2?0:1);
		for(int i=n-1;i<n+w;i++){
			if(par==0) G.add_directed_edge(s+OFSET,i+OFSET,INF);
			else       G.add_directed_edge(i+OFSET,t+OFSET,INF);
			par=1-par;
		}

		int tmp=Dinic(G,s+OFSET,t+OFSET);

		if(tmp<ans){
			vector<int> S=minimum_cut(G,s+OFSET,t+OFSET);
			vector<int> y(n,1);
			rep(i,S.size()) if(0+OFSET<=S[i] && S[i]<n+OFSET) y[S[i]-OFSET]=0;
			vector<int> x(n);
			rep(i,n) x[i]=(i%2==0?y[i]:1-y[i]);
			vector<int> k(n);
			rep(i,n) k[i]=(x[i]-(i>0?x[i-1]:0)+2)%2;

			ans=tmp;
			seq=k;
		}
	}

	rep(i,n) printf("%d",seq[i]);
	puts("");

	return 0;
}