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<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
#include<numeric>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

class Edge{
public:
    Int from, to, rev;
    Int cost, lim;
    Edge(Int from, Int to, Int cost, Int lim = -1, Int rev = -1):
        from(from),to(to),cost(cost),lim(lim),rev(rev){}
};


class Graph{
public:
    Int n;
    Int m;
    vector<vector<Edge>> edge;
    Graph(Int n = 0):n(n),m(0){
        edge = vector<vector<Edge>>(n);
    }
    void add_edge(Int from, Int to, Int cost = 1, Int lim = -1)
        {
            if(lim == -1){
                edge[from].push_back(Edge(from, to, cost));
                return;
            }
            edge[from].push_back(Edge(from, to, cost, lim, edge[to].size()));
            edge[to].push_back(Edge(to, from, -cost, 0, edge[from].size() - 1));
        }
};



class Dinic{
public:
    Graph *g;
    vector<int> iter, level, come;

    Dinic(){};
    void bfs(int s){
        queue<int> q;
        fill(level.begin(), level.end(), INF);
        level[s] = 0;
        q.push(s);
        while(!q.empty()){
            int x = q.front();q.pop();
            for(auto e:g->edge[x]){
                if(level[e.to] != INF)continue;
                if(e.lim <= 0)continue;
                level[e.to] = level[x] + 1;
                q.push(e.to);
            }
        }
    }

    Int dfs(int s, int t, Int f){
        if(s == t)return f;
        if(come[s])return 0;
        come[s] = true;
        for(int &i = iter[s];i < g->edge[s].size();i++){
            Edge &e = g->edge[s][i];
            if(e.lim <= 0)continue;
            Int tmp = dfs(e.to, t, min(f, e.lim));
            if(tmp == 0)continue;
            e.lim -= tmp;
            g->edge[e.to][e.rev].lim += tmp;
            return tmp;
        }
        return 0;
    }
    Int max_flow(Graph &_g, int s, int t){
        g = &_g;
        iter = vector<int>(g->n);
        level = vector<int>(g->n);
        come = vector<int>(g->n, 0);
        Int res = 0;
        while(true){
            bfs(s);
            if(level[t] == INF)break;
            fill(iter.begin(), iter.end(), 0);
            while(true){
                fill(come.begin(), come.end(), false);
                Int tmp = dfs(s, t, INF);
                if(tmp == 0)break;
                else res += tmp;
            }
        }
        return res;   
    }  
};

void dfs(Graph &g, int x, vector<int> &come){
    if(come[x])return;
    come[x] = true;
    for(auto e:g.edge[x]){
        if(e.lim == 0)continue;
        dfs(g, e.to, come);
    }
}

vector<int> reachable(Graph &g, int s){
    vector<int> come(g.n);
    dfs(g, s, come);
    return come;
}

pair<Int, string> calc(int after, int w, vector<Int> &a, vector<Int> &b){
    int n = a.size();
    Graph g(n + 2*w + 3);
    int S = n + 2*w + 1, T = n + 2*w + 2, base = w+1;
    for(int i = 0;i < n;i++){
        int l = base + i - 1, r = base + i;
        g.add_edge(l, r, 1, a[i]);
        g.add_edge(r, l, 1, a[i]);
    }
    for(int i = 0;i < n;i++){
        int l = base + i - w - 1, r = base + i + w;
        g.add_edge(l, r, 1, b[i]);
        g.add_edge(r, l, 1, b[i]);
    }
    for(int i = 0;i < base;i++){
        if(i % 2 == 0)g.add_edge(S, i, 1, LINF);
        if(i % 2 == 1)g.add_edge(i, T, 1, LINF);
    }
    for(int i = w + n;i <= w + n + w;i++){
        if(i % 2 == after)g.add_edge(S, i, 1, LINF);
        if(i % 2 != after)g.add_edge(i, T, 1, LINF);
    }
    Dinic d;
    Int mf = d.max_flow(g, S, T);
    auto r = reachable(g, S);
    string ans = "";
    for(int i = 0;i < n;i++){
        int ind = base + i;
        if(r[ind] == ind % 2)ans.push_back('1');
        else ans.push_back('0');
    }
    for(int i = n-1;i > 0;i--){
        if(ans[i] != ans[i-1])ans[i] = '1';
        else ans[i] = '0';
    }
    return make_pair(mf, ans);
}

int main(){
    int n, w;
    cin >> n >> w;
    vector<Int> a(n), b(n);
    for(auto &e:a)cin >> e;
    for(auto &e:b)cin >> e;
    auto zero_ans = calc(0, w, a, b);
    auto one_ans = calc(1, w, a, b);
//    cout << zero_ans.first << " " << zero_ans.second << endl;
//    cout << one_ans.first << " " << one_ans.second << endl;
    if(zero_ans.first < one_ans.first)cout << zero_ans.second << endl;
    else cout << one_ans.second << endl;
    return 0;
}