#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t I;
#define L(T) (T == 1 ? 10 : T == 2 ? 20 : 128)
int pigeon_num(int T, int k) {
	return k + 1 << 7;
}

string send(int T, int n, int k, I msg) {
	string r;
	for (int i=0; i<128; i++)
		r += string (k + 1, msg >> i & 1 ? '1' : '0');
	return r;
}

I receive(int T, int k, const string &msg) {
	I r = 0;
	int x[128]; string t = msg;
	for (int i=0; i<128; i++) {
		x[i] = t[i*(k+1)] - '0';
		for (int j=i*(k+1)+1, p=j; j<(i+1)*(k+1); j++)
			if (t[j] ^ t[j-1]) {
				p = max(p, j);
				while (t[p] ^ t[j-1]) p ++;
				swap(t[j], t[p]);
			}
	}
	for (int i=127; ~i; i--)
		(r <<= 1) |= x[i];
	return r;
}