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 "bits/stdc++.h"

#pragma warning(disable:4996)
using namespace std;


#define _GLIBCXX_DEBUG

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


//const int INF = 2147483647;
//const long long int L_INF = 9223372036854775807;

typedef  int Weight;

const Weight INF = 1e9+10;
const Weight ZERO = 0;
struct Edge {
	int src, dst;
	Weight weight;
	int id;
	Edge(int src_, int dst_, Weight weight_, const int id_) :
		src(src_), dst(dst_), weight(weight_), id(id_) { }
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
	Edge() :src(0), dst(0), weight(0) {

	}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph&g, const int s,const int t,const Weight weight) {
	g[s].push_back(Edge(s,t,weight));
}
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])

int N, M;
const int T = 3100;
const int X = 1001;
string nans;
long long int answer=1e18;
//流量0の逆辺も張らないと正しく求まらないので注意
Weight maximumFlow(Graph &g, int s, int t) {
	Graph ag(g);
	for (int i = 0; i < ag.size(); ++i) {
		for (int j = 0; j < ag[i].size(); ++j) {
			int d = ag[i][j].dst;
			int s = ag[i][j].src;

			bool ok = false;
			for (int k = 0; k < ag[d].size(); ++k) {
				if (ag[d][k].src == s) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				g[d].push_back(Edge(d, s, ZERO));
			}
		}
	}
	int n = g.size();
	Matrix flow(n, Array(n,ZERO)), capacity(n, Array(n,ZERO));
	REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] =capacity[e->src][e->dst]+ e->weight;


	Weight total = ZERO;
	while (1) {
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > ZERO) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0)break; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j]){
			auto v(RESIDUE(prev[j], j));
			if (inc > v) {
				inc = v;
			}
		}
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]][j] =flow[prev[j]][j]+inc, flow[j][prev[j]] =flow[j][prev[j]]- inc;;
		total += inc;
	}
	string st;
	{
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > ZERO) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		for (int i = X+1; i < 1+X + N; ++i) {
			int l_ok=(prev[i]==-1)^(i%2);
			int r_ok=(prev[i-1]==-1)^((i+1)%2);
			st.push_back('0'+(l_ok!=r_ok));
		}
	}
	if (total < answer) {
		answer=total;
		nans=st;
	}
	return total;
}
int main() {cin>>N>>M;
	vector<int>as(N);
	vector<int>bs(N);
	for(int i=0;i<N;++i)cin>>as[i];
	for(int i=0;i<N;++i)cin>>bs[i];
	long long int sum=accumulate(as.begin(),as.end(),0)+accumulate(bs.begin(),bs.end(),0);
	const int start=0;
	const int in_a=start+1;

	const int goal=in_a+T;
	for(int flag=0;flag<2;++flag){
		Graph g(goal+1);
		for (int i = 0; i < X; ++i) {
			long long int cost=i%2?0:INF;
			add_edge(g,start,in_a+i,cost);
			add_edge(g,in_a+i,goal,INF-cost);
		}
		for (int i = X; i < X + N; ++i) {
			add_edge(g,in_a+i,in_a+i-1,as[i-X]);
			add_edge(g, in_a + i-1, in_a + i, as[i - X]);

			add_edge(g,in_a+i-M-1,in_a+i+M,bs[i-X]);
			add_edge(g, in_a + i + M, in_a + i - M-1, bs[i - X]);

			if (i != X + N - 1) {
				add_edge(g, start, in_a + i, 0);
				add_edge(g, in_a + i, goal, 0);
			}
		}
		for (int i = X + N-1; i < T; ++i) {
			long long int cost=(i+flag)%2?0:INF;
			add_edge(g,start,in_a+i,cost);
			add_edge(g,in_a+i,goal,INF-cost);
			
		}

		Weight w=maximumFlow(g,start,goal);

	}
	cout<<nans<<endl;
	return 0;
}