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 <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;

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

const int INF = int(1.05e9);


typedef int flow_t;
const flow_t FLOW_INF = (int)(1.05e9);
const flow_t FLOW_EPS = 0;

struct Edge {
	int to, revIndex;
	flow_t capacity;

	Edge() {}
	Edge(int to_, int revIndex_, flow_t capacity_):
		to(to_), revIndex(revIndex_), capacity(capacity_)
	{}
};

struct Graph : vector< vector<Edge> > {
	int numV;
	vector<int> level;
	vector<int> iter;

	Graph(){}

	void init(int numV_) {
		numV = numV_;
		assign(numV, vector<Edge>());
	}

	void init() {
		assign(numV, vector<Edge>());
	}

	void addUndirectedEdge(int from, int to, flow_t cap) {
		at(from).push_back(Edge(to, (int)at(to).size(), cap));
		at(to).push_back(Edge(from, (int)at(from).size() - 1, cap));
	}

	void addDirectedEdge(int from, int to, flow_t cap) {
		at(from).push_back(Edge(to, (int)at(to).size(), cap));
		at(to).push_back(Edge(from, (int)at(from).size() - 1, 0));
	}
};

flow_t augment(Graph& graph, int v, const int sink, flow_t f) {
	if (v == sink) {
		return f;
	}
	for (int &i = graph.iter[v]; i < (int)graph[v].size(); ++i) {
		Edge &e = graph[v][i];
		if (e.capacity > FLOW_EPS && graph.level[v] < graph.level[e.to]) {
			flow_t neck = augment(graph, e.to, sink, min(e.capacity, f));
			if (neck > FLOW_EPS) {
				e.capacity -= neck;
				graph[e.to][e.revIndex].capacity += neck;
				return neck;
			}
		}
	}
	return 0;
}

flow_t calcMaxFlow(Graph& graph, const int source, const int sink) {
	flow_t flow = 0;
	graph.level.resize(graph.numV);
	graph.iter.resize(graph.numV);
	for (;;) {

		fill(graph.level.begin(), graph.level.end(), -1);
		queue<int> que;
		graph.level[source] = 0;
		que.push(source);

		for (;!que.empty();) {
			int v = que.front(); que.pop();
			for (int i = 0; i < (int)graph[v].size(); ++i) {
				Edge &e = graph[v][i];
				if (e.capacity > FLOW_EPS && graph.level[e.to] < 0) {
					graph.level[e.to] = graph.level[v] + 1;
					que.push(e.to);
				}
			}
		}

		if (graph.level[sink] < 0) {
			break;
		}
		fill(graph.iter.begin(), graph.iter.end(), 0);
		flow_t add;
		for (;(add = augment(graph, source, sink, FLOW_INF)) > FLOW_EPS;) {
			flow += add;
		}
	}
	return flow;
}

void traverse(Graph& graph, int v, bool vis[]) {
	for (int i = 0; i < int(graph[v].size()); ++i) {
		const Edge &e = graph[v][i];
		const int u = e.to;
		if (!vis[u] && e.capacity > 0) {
			vis[u] = true;
			traverse(graph, u, vis);
		}
	}
}

int main(){
	int n, w;
	scanf("%d%d", &n, &w);
	int as[1000], bs[1000];
	rep(i,n) scanf("%d", as+i);
	rep(i,n) scanf("%d", bs+i);

	int ans[1000];
	int best = -1;
	rep(total,2){
		int score = accumulate(as,as+n,0) + accumulate(bs,bs+n,0);
		Graph g;
		g.init(n+2*w+3);
		int s = n + 2*w + 1, t = s + 1;
		g.addDirectedEdge(0,t,INF);
		rep(i,w){
			if(i&1) g.addDirectedEdge(i+1,t,INF);
			else g.addDirectedEdge(s,i+1,INF);
		}
		rep(i,w+1){
			if((w+n+i+total)&1) g.addDirectedEdge(n+w+i,t,INF);
			else g.addDirectedEdge(s,n+w+i,INF);
		}
		rep(i,n) g.addUndirectedEdge(i,i+2*w+1,bs[i]);
		rep(i,n) g.addUndirectedEdge(w+i,w+i+1,as[i]);
		score -= calcMaxFlow(g,s,t);
		if (best < score) {
			best = score;
			bool visited[3333] = {false};
			traverse(g, s, visited);
			rep(i,n) ans[i] = (visited[i+w] == visited[i+w+1] ? 1 : 0);
		}
	}

	rep(i,n) printf("%d", ans[i]);
	puts("");
//	printf("%d\n", best);
	return 0;
}