#include <string>
#include <vector>
#include <cassert>
#include <cstring>

//you may define some global variables, but it does not work if you try to transfer any information from function pigeon_num or send to function receive through these variables.

bool add(__uint128_t &x, __uint128_t y){
	if(x<=~y){
		x+=y;
		return 0;
	}
	else{
		x=0;
		x=~x;
		return 1;
	}
}

__uint128_t f[1444][5];
__uint128_t g[1444][5];
__uint128_t sum[1444][5][1444];
int type[2111];
const int to[4][5]={
	{-1,-1,-1,3,2},
	{2,3,2,3,2},
	{-1,1,0,1,0},
	{0,1,0,1,0}
};
const char col[6]="1100";

class Init{
    const static int L=1300;
public:
    int m;
	Init(int k){
		//you may do some initialization for RECEIVE function here
        int i=0;
        memset(f,0,sizeof(f));
        f[0][1]=1;
        f[0][3]=1;
        for(int j=1;j<=2*k;++j)type[j]=0;
        for(int j=2*k+2;j<=3*k;++j)type[j]=2;
        for(int j=3*k+1;j<=L;++j)type[j]=4;
        type[2*k+1]=1;
        for(int j=4*k+2;j<=L;j+=2*k+1)type[j]=3;
        int ok=0;
        while(!ok){
            for(int t=0;t<4;++t){
                if(f[i][t]){
                    auto tmp=f[i][t];
                    for(int j=1;i+j<=L;++j){
                        if(to[t][type[j]]!=-1){
                            add(f[i+j][to[t][type[j]]],tmp);
                        }
                    }
                }
            }
            ++i;
            __uint128_t tmp=0;
            for(int t=0;t<4;++t){
                ok|=add(tmp,f[i][t]);
            }
        }
        m=i;
        for(int j=0;j<4;++j){
            g[m][j]=1;
        }
        for(int i=m-1;i>=0;--i){
            for(int t=0;t<4;++t){
                g[i][t]=0;
                for(int j=1;i+j<=m;++j){
                    sum[i][t][j]=sum[i][t][j-1];
                    if(to[t][type[j]]!=-1){
                        add(g[i][t],g[i+j][to[t][type[j]]]);
                        add(sum[i][t][j],g[i+j][to[t][type[j]]]);
                    }
                }
            }
        }
	}
};

/*
Taskid:         The index of the subtask. If it is subtask 2, then Taskid=2.
k:              The time threshold. Suppose the i-th pigeon taking off is the p_i-th one to land. It is guaranteed that abs(i-p_i)<=k.
return value:   The number of pigeons Little E will use.
*/
int pigeon_num(int Taskid, int k){
	//you may do some initialization for SEND function here
	Init init(k);
	return init.m;
}

/*
Taskid:         The index of the subtask. If it is subtask 2, then Taskid=2.
n:              The number of pigeons Little E will use. This equals the return value of function pigeon_num.
k:              The time threshold. Suppose the i-th pigeon taking off is the p_i-th one to land. It is guaranteed that abs(i-p_i)<=k.
msg:            The content of the message.
return value:   The order of the pigeons taking off. The length of this string must be n. return_value[i]='0' means the (i+1)-th pigeon taking off is black. return_value[i]='1' means the (i+1)-th pigeon taking off is white.
*/
std::string send(int Taskid, int n, int k, __uint128_t msg){
	int st=1;
    int now=0;
    std::string ret;
    if(msg>=sum[0][1][n]){
        st=3;
        msg-=sum[0][1][n];
    }
    while(now<n){
        int ans=-1;
        for(int l=1,r=n-now,mid=l+r>>1;l<=r;mid=l+r>>1){
            if(msg<sum[now][st][mid])ans=mid,r=mid-1;
                else l=mid+1;
        }
        assert(ans!=-1);
        ret+=std::string(ans, col[st]);
        msg-=sum[now][st][ans-1];
        st=to[st][type[ans]];
        now+=ans;
    }
    return ret;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int _next[2222][2];
const auto next=_next+1;

/*
Taskid:         The index of the subtask. If it is subtask 2, then Taskid=2.
k:              The time threshold. Suppose the i-th pigeon taking off is the p_i-th one to land. It is guaranteed that abs(i-p_i)<=k.
msg:			The order of the pigeons landing. Its length is equal to n. msg[i] denotes the color of the (i+1)-th pigeon watched landing by Little F. '0' means black and '1' means white.
return value:	The content of the message. It should be correct.
*/
__uint128_t receive(int Taskid, int k, const std::string &msg){
	const static Init init(k);
    int n=msg.size();
    next[n-1][0]=next[n-1][1]=n;
    for(int i=n-2;i>=-1;--i){
        next[i][0]=next[i+1][0];
        next[i][1]=next[i+1][1];
        next[i][msg[i+1]-'0']=i+1;
    }
	int tofind=0;
    int now=-1;
    std::string code;
    while(1){
        //printf("%d\n",now);
        if(next[now][tofind]==n){
            while(code.size()<n){
                code+=tofind^'1';
            }
            break;
        }
        std::vector<int> pl;
        for(int i=1;i<=2*k+1&&next[now][tofind]<n;++i){
            now=next[now][tofind];
            pl.push_back(now);
        }
        if(pl.size()==2*k+1&&pl[k]-pl[0]<=2*k&&pl[2*k]-pl[k]<=2*k){
            while(code.size()<pl[k]-k){
                code+=tofind^'1';
            }
            while(code.size()<pl[k]+k+1){
                code+=tofind^'0';
            }
        }
        else{
            int realnum=pl.size();
            int near=pl[0]<=code.size()+k;
            if(!near){
                int left=code.size()+(pl[0]-code.size()+k)/(2*k+1)*(2*k+1);
                for(int i=1;i<pl.size();++i){
                    if(pl[i]-left>i+k){
                        realnum=i;
                        break;
                    }
                }
            }
            else{
                for(int i=1;i<pl.size();++i){
                    if(pl[i]-code.size()>i+k){
                        realnum=i;
                        break;
                    }
                }
            }
            if(!near||code.size()==0){
                int num1=(pl[0]-code.size()+k)/(2*k+1)*(2*k+1);
                code+=std::string(num1, tofind^'1');
                code+=std::string(realnum, tofind^'0');
                if(code.size()==n){
                    break;
                }
                code+=std::string(2*k+1, tofind^'1');
                now=code.size()-1;
            }
            else{
                code+=std::string(realnum, tofind^'0');
                now=pl[realnum-1];
            }
        }
    }
    __uint128_t ans=0;
    int st=1;
    if(code[0]=='0')ans=sum[0][1][n],st=3;
    int pre=0;
    int len=1;
    for(now=0;now<n;++now){
        if(now==n-1||code[now]!=code[now+1]){
            ans+=sum[pre][st][len-1];
            pre+=len;
            st=to[st][type[len]];
            len=1;
        }
        else{
            ++len;
        }
    }
    return ans;
}