#include "nth.h"
#include<bits/stdc++.h>
using namespace std;

namespace Alice
{
    int cnt,m,n,a[5000000],pos=20,L=0,R=(1<<21)-1,ty;

    void sol()
    {
        if(n<=2)
        {
            for(int i=1;i<=n;i++)for(int j=20;j>=0;j--)sendA((a[i]>>j)&1);
            return;
        }
        int p=(n+1)/2;
        sendA((a[p]>>pos)&1);
    }

    void initA(std::bitset<M> A, unsigned S,unsigned c)
    {
        for(int i=0;i<M;i++)if(A[i])a[++n]=i;
        m=S-n;
        if(c<=min(n,m))n=c,ty=0;
        else if(c<=max(n,m))
        {
            if(n>m)
            {
                for(int i=c-m;i<=c;i++)a[i-(c-m)+1]=a[i];
                n=m+1;
            }
            else
            {
                n++;
                for(int i=n;i;i--)a[i]=a[i-1];
            }
            c=n+1;ty=1;
        }
        else
        {
            for(int i=c-m;i<=n;i++)a[i-(c-m)+1]=a[i];
            n=n-c+m+1;c=n+1;ty=1;
        }
        sol();
        // cerr<<"find A "<<ty<<'\n';
        // for(int i=1;i<=n;i++)cerr<<a[i]<<' ';puts("");
    }

    void receiveA(bool w)
    {
        int p=(n+1)/2,x=(a[p]>>pos)&1;w^=x;
        if(w>x)
        {
            for(int i=p;i<=n;i++)a[i-p+1]=a[i];
            n-=p-1;
        }
        if(w<x)n=p;
        if(w==x)
        {
            int val=(a[p]>>pos)<<pos;
            int l=val,r=val+(1<<pos)-1;
            // cerr<<"exexexexA "<<l<<' '<<r<<' '<<val<<' '<<pos<<'\n';
            for(int i=1;i<=n;i++)a[i]=min(r,a[i]),a[i]=max(l,a[i]);
        }
        // cerr<<"A "<<n<<' '<<p<<' '<<pos<<' '<<x<<' '<<w<<'\n';
        // for(int i=1;i<=n;i++)cerr<<a[i]<<' ';cerr<<'\n';
        pos-=!(w^x);sol();
    }
}

namespace Bob
{
    int m,n,a[5000000],pos=20,L=0,R=(1<<21)-1,ty;

    void initB(std::bitset<M> A, unsigned S,unsigned c)
    {
        for(int i=0;i<M;i++)if(A[i])a[++n]=i;
        m=S-n;
        if(c<=min(n,m))n=c,ty=0;
        else if(c<=max(n,m))
        {
            if(n>m)
            {
                for(int i=c-m;i<=c;i++)a[i-(c-m)+1]=a[i];
                n=m+1;
            }
            else
            {
                n++;
                for(int i=n;i;i--)a[i]=a[i-1];
            }
            c=n+1;ty=1;
        }
        else
        {
            for(int i=c-m;i<=n;i++)a[i-(c-m)+1]=a[i];
            n=n-c+m+1;c=n+1;ty=1;
        }
        // cerr<<"find B "<<ty<<'\n';
        // for(int i=1;i<=n;i++)cerr<<a[i]<<' ';puts("");
    }

    int cnt=0,re[50]={0,0,0},hv=1;

    void receiveB(bool x)
    {
        if(n<=2)
        {
            // cerr<<x<<' ';
            int z=x;
            re[hv]<<=1,re[hv]|=x;cnt++;
            if(cnt==21)
            {
                cnt=0;++hv;
                // puts("");
                if(hv>n)
                {
                    for(int i=1;i<=n;i++)re[hv++]=a[i];
                    std::sort(re+1,re+hv);
                    report(ty?re[n+1]:re[n]);
                }
            }
            return;
        }
        int p=n/2+1,w=(a[p]>>pos)&1;
        if(w<x)
        {
            for(int i=p;i<=n;i++)a[i-p+1]=a[i];
            n-=p-1;
        }
        if(w>x)n=p;
        if(w==x)
        {
            if(!pos)report(a[1]);
            int val=(a[p]>>pos)<<pos;
            int l=val,r=val+(1<<pos)-1;
            for(int i=1;i<=n;i++)a[i]=min(r,a[i]),a[i]=max(l,a[i]);
        }
        pos-=!(w^x);sendB(w^x);
        // cerr<<"B "<<n<<' '<<p<<' '<<pos<<' '<<x<<' '<<w<<'\n';
        // for(int i=1;i<=n;i++)cerr<<a[i]<<' ';cerr<<'\n';
    }
}