#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int > 
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128	
using namespace std;
const int N = 1e6 + 7;
#define u128 __uint128_t
const u128 qwq = ((u128) 1) << 127;

vi PT;

u128 dp[N], sum[N];

int k, mnl, inited, cnt;
void Init(int K) {
	if(inited) return ;
	cnt = 0;
	k = K, mnl = k * 2 + 1;
	inited = true;
	while(dp[cnt] < qwq) {
		++cnt;
		dp[cnt] = 1; 
		L(i, 0, cnt - mnl) {
			dp[cnt] += dp[i];
			dp[cnt] = min(dp[cnt], qwq);
		}
	} 
}

int pigeon_num(int Taskid, int k) {
	Init(k);
	return cnt;
}
std::string send(int Taskid, int n, int k, __uint128_t msg) {
	Init(k);
	int col = msg & 1;
	u128 ret = msg >> 1;
	string s;
	int cur = cnt;
	while(cur) {
		if(!ret) {
			L(t, 1, cur) s += col + '0';
			break;
		}
		ret -= 1;
		L(j, mnl, cur) {
			if(ret < dp[cur - j]) {
				L(t, 1, j) 
					s += col + '0';
				cur -= j;
				col ^= 1;
				break;
			} else {
				ret -= dp[cur - j];
			}
		}
	}
	return s;
}
int col[N], len[N], tp;
__uint128_t receive(int Taskid, int k, const std::string &msg) {
	Init(k);
	tp = 0;
	string s = msg;
	int pos = 0;
	while(pos < sz(s)) {
		int w = s[pos] - '0';
		int j = pos;
		while(j < sz(s) && s[j + 1] == w + '0') ++j;
		while(true) {
			int p = -1;
			L(t, j + 1, min(j + k + 1, sz(s) - 1)) if(s[t] == w + '0') {
				p = t;
				break;
			}
			if(p == -1) break;
			R(t, p, j + 2) swap(s[t], s[t - 1]);
			++j;
		}
		col[++tp] = w;
		len[tp] = j - pos + 1;
		pos = j + 1;
	}
	u128 ret = 0;
	int cur = cnt;
	L(i, 1, tp) {
		if(i != tp) ret += 1;
		else break;
		L(j, mnl, len[i] - 1) 
			ret += dp[cur - j];
		cur -= len[i];
	}
	ret <<= 1;
	if(col[1] & 1) ret += 1;
	return ret;
}