Problem: The popular improv website Interpretation Impetus hosts regular improv contests and maintains a rating of the best performers. However, since improv can often go horribly wrong, the website is notorious for declaring improv contests unrated. It now holds a wager before each improv contest where the participants try to predict whether it will be rated or unrated, and they are now more popular than the improv itself.

Izzy and n other participants take part in each wager. First, they each make their prediction, expressed as 1 ("rated") or 0 ("unrated"). Izzy always goes last, so she knows the predictions of the other participants when making her own. Then, the actual competition takes place and it is declared either rated or unrated.

You need to write a program that will interactively play as Izzy. There will be m wagers held in 2021, and Izzy's goal is to have at most 1.3⋅ b + 100 wrong predictions after all those wagers, where b is the smallest number of wrong predictions that any other wager participant will have after all those wagers. 

The number b is not known in advance. Izzy also knows nothing about the other participants — they might somehow always guess correctly, or their predictions might be correlated. Izzy's predictions, though, do not affect the predictions of the other participants and the decision on the contest being rated or not — in other words, in each test case, your program always receives the same inputs, no matter what it outputs.

Interaction

First, a solution must read two integers n (1 ≤ n ≤ 1000) and m (1 ≤ m ≤ 10 000). Then, the solution must process m wagers. For each of them, the solution must first read a string consisting of n 0s and 1s, in which the i-th character denotes the guess of the i-th participant. Then, the solution must print Izzy's guess as 0 or 1. Don't forget to flush the output after printing it! Then, the solution must read the actual outcome, also as 0 or 1, and then proceed to the next wager, if this wasn't the last one. 

Your solution will be considered correct if it makes at most 1.3⋅ b + 100 mistakes, where b is the smallest number of mistakes made by any other participant. Note that if a solution outputs anything except 0 or 1 for a wager, it will be considered incorrect even if it made no other mistakes. 

There are 200 test cases in this problem.

Example

Input


3 4
000

1
100

1
001

0
111

1


Output




0


0


1


1

Note

In the example, the participants made 1, 2, and 3 mistakes respectively, therefore b=1 (the smallest of these numbers). Izzy made 3 mistakes, which were not more than 1.3⋅ b + 100=101.3, so these outputs are good enough to pass this test case (as are any other valid outputs).

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f
#define rep(i,a,n) for(int i=(a),__##i=(n);i<=__##i;++i)
#define repe(i,a,n) for(int i=(a),__##i=(n);i<__##i;++i)
#define repv(i,n,a) for(int i=(n),__##i=(a);i>=__##i;--i)
#define repl(i,a,n) for(ll i=(a),__##i=(n);i<=__##i;++i)
#define lowbit(x) ((x)&-(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define mkp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define X first
#define Y second
#define ll long long
#define maxn 505
#define maxm 20
using namespace std;
inline ll read(){
    ll s=0,f=1; char c=getchar();
    while(c<'0'||c>'9') f*=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*f;
}

inline double random(double l, double r){
    return (r-l)*rand()/RAND_MAX+l;
}
inline int getMax(const vector<double> &v){
    return max_element(v.begin(), v.end())-v.begin();
}

double sigmoid(double x){
    return 1/(1+exp(-x));
}
double desigmoid(double y){
    return y*(1-y);
}

struct Node{
    double value, delta;
    Node(){}
    Node(double x):value(x){}
};

struct Net{
    int inSize, outSize;
    virtual void forwardPropagation(vector<Node> &in, vector<Node> &out){}
    virtual void backPropagation(vector<Node> &out, vector<Node> &in, double learningRate){}\
};

class FC: public Net{
    double (*activate)(double x);
    double (*deactivate)(double y);
protected:
    vector<vector<double>> weight;
    vector<double> bias;
    void init(int in, int out){
        inSize=in, outSize=out;
        weight.resize(in);
        for(auto &x:weight) x.resize(out);
        bias.resize(out);
    }
    void init(int in, int out, double val){
        inSize=in, outSize=out;
        bias.resize(out);
        for(auto &i:bias) i=random(-val, val);
        weight.resize(in);
        for(auto &x:weight){
            x.resize(out);
            for(auto &i:x) i=random(-val, val);
        }
    }
public:
    FC(){}
    FC(int in, int out, double val){ init(in, out, val); }
    FC(int in, int out, double val, double (*f)(double x), double (*df)(double y)){
        init(in, out, val);
        activate=f, deactivate=df;
    }
    void forwardPropagation(vector<Node> &in, vector<Node> &out){
        assert(inSize==in.size()&&outSize==out.size());
        for(int o=0; o<outSize; o++){
            out[o].value=bias[o];
            for(int i=0; i<inSize; i++) out[o].value+=in[i].value*weight[i][o];
            out[o].value=activate(out[o].value);
        }
    }
    void backPropagation(vector<Node> &out, vector<Node> &in, double learningRate){
        assert(inSize==in.size()&&outSize==out.size());
        vector<vector<double>> wDelta(weight);
        vector<double> bDelta(bias);
        for(int o=0; o<outSize; o++) bDelta[o]=out[o].delta*deactivate(out[o].value);
        for(int i=0; i<inSize; i++){
            in[i].delta=0;
            for(int o=0; o<outSize; o++){
                in[i].delta+=bDelta[o]*weight[i][o];
                wDelta[i][o]=bDelta[o]*in[i].value;
                weight[i][o]-=wDelta[i][o]*learningRate;
            }
        }
        for(int o=0; o<outSize; o++) bias[o]-=bDelta[o]*learningRate;
    }
};

class Softmax: public FC{
public:
    Softmax(int in, int out, double val){ init(in, out, val); }
    void forwardPropagation(vector<Node> &in, vector<Node> &out){
        assert(inSize==in.size()&&outSize==out.size());
        for(int o=0; o<outSize; o++){
            out[o].value=bias[o];
            for(int i=0; i<inSize; i++) out[o].value+=in[i].value*weight[i][o];
        }
        double tot=0;
        for(int o=0; o<outSize; o++) tot+=out[o].value=exp(out[o].value);
        for(int o=0; o<outSize; o++) out[o].value/=tot;
    }
    void backPropagation(vector<Node> &out, vector<Node> &in, double learningRate){
        assert(inSize==in.size()&&outSize==out.size());
        vector<vector<double>> wDelta(weight);
        vector<double> bDelta(bias);
        for(int o=0; o<outSize; o++) bDelta[o]=out[o].delta;
        for(int i=0; i<inSize; i++){
            in[i].delta=0;
            for(int o=0; o<outSize; o++){
                in[i].delta+=bDelta[o]*weight[i][o];
                wDelta[i][o]=bDelta[o]*in[i].value;
                weight[i][o]-=wDelta[i][o]*learningRate;
            }
        }
        for(int o=0; o<outSize; o++) bias[o]-=bDelta[o]*learningRate;
    }
};
class BP{
    int netSize;
    vector<Net *> nets;
    vector<vector<Node>> layers;
public:
    BP(){ netSize=0, layers.resize(1); }
    void addNet(Net *net){
        nets.push_back(net), netSize++;
        layers.push_back(vector<Node>(net->outSize));
    }
    vector<double> work(const vector<double> &in){
        layers[0].resize(in.size());
        for(int i=0; i<in.size(); i++) layers[0][i]=in[i];
        for(int i=0; i<netSize; i++){
            nets[i]->forwardPropagation(layers[i], layers[i+1]);
        }
        vector<double> ret;
        for(auto &x:layers[netSize]) ret.push_back(x.value);
        return ret;
    }
    void update(const vector<double> &err, double learningRate){
        for(int i=0; i<err.size(); i++) layers[netSize][i].delta=err[i];
        for(int i=netSize-1; i>=0; i--){
            nets[i]->backPropagation(layers[i+1], layers[i], learningRate);
        }
    }
};

BP bp;
double learningRate=0.01;

int hidden=15;
double randomRange=0.5;

void train(const vector<double> &in){
    vector<double> err=bp.work(in);
    int predict=getMax(err);
    cout<<predict<<endl;
    fflush(stdout);
    int ans=read();
    for(int t=0; t<2; t++) err[t]=err[t]-(t==ans);
    bp.update(err, learningRate);
}

int main(){
    srand(time(0));
    int n=read(),m=read();
    bp.addNet(new FC(n, hidden, randomRange, sigmoid, desigmoid));
    bp.addNet(new Softmax(hidden, 2, randomRange));
    while(m--){
        string s; cin>>s;
        vector<double> in;
        for(auto c:s) in.push_back(c-'0');
        train(in);
    }
    return 0;
}