#include <bits/stdc++.h>
#define ll long long
#define maxn 1100005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
const int r2 = 21; 
struct th {
	vector<vi> s;
	int sum;
	void init(int k) {
		sum = 0;
		s.resize(k + 1);
		for (int i = 0; i <= k; i++) {
			s[i].resize(1 << i);
			for (int j = 0; j < s[i].size(); j++)
				s[i][j] = 0;
		}
	}
	void ch(pi pl, int num) {
		s[pl.fi][pl.se] += num, sum += num;
	}
}nr[1 << r2], sr[1 << r2];

vector<pi> nx[r2][2];
char inp[1 << r2];
int main() {
	for (int i = 0; i < r2; i++)
		for (int k = 0; k < 2; k++) {
			nx[i][k].resize(1 << i);
			for (int j = 0; j < (1 << i); j++) {
				if (i == 0) nx[i][k][j] = mp(-1, 0);
				else {
					int rr = j & (1 << (i - 1));
					if (rr && k) nx[i][k][j] = mp(i - 1, j ^ (1 << (i - 1)));
					else if (rr == 0 && k == 0) nx[i][k][j] = mp(i - 1, j);
					else nx[i][k][j] = nx[i - 1][k][j % (1 << (i - 1))];
				}
			}
		}
	int n, k;
	cin >> n >> k;
	int nl = 0, res = 0;
	nr[0].init(n);
	for (int i = 0; i <= n; i++) {
		scanf("%s", inp);
		for (int j = 0; j < (1 << i); j++)
			if (inp[j] == '1') nr[0].ch(mp(i, j), 1);
	}
	for (int tt = 1; tt <= n; tt++) {
	//	cout << "!!!" << tt << endl;
		for (int m = 0; m < (1 << tt); m++)
			sr[m].init(n - tt);
		for (int m = 0; m < (1 << (tt - 1)); m++)
			for (int s = 0; s <= n - tt + 1; s++)
				for (int q = 0; q < nr[m].s[s].size(); q++)
					for (int r = 0; r < 2; r++)
						if (!nr[m].s[s][q]) continue;
						else {
							pi ed = nx[s][r][q];
							if (ed.fi != -1)
								sr[m * 2 + r].ch(ed, nr[m].s[s][q]);
						}
		for (int m = 0; m < (1 << tt); m++)
			if (sr[m].sum >= k) {
				nl = tt;
				res = m;
				break;
			}
		for (int m = 0; m < (1 << tt); m++)
			nr[m] = sr[m];
	}
	vi otp(nl);
	for (int i = 0; i < nl; i++)
		otp[i] = res % 2, res /= 2;
	for (int i = nl - 1; i >= 0; i--)
		printf("%d", otp[i]);
	printf("\n");
	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

You are given a set S of strings consisting of `0` and `1`, and an integer K.

Find the longest string that is a subsequence of K or more different strings in S. If there are multiple strings that satisfy this condition, find the lexicographically smallest such string.

Here, S is given in the format below:

* The data directly given to you is an integer N, and N+1 strings X_0,X_1,...,X_N. For every i (0\leq i\leq N), the length of X_i is 2^i.
* For every pair of two integers (i,j) (0\leq i\leq N,0\leq j\leq 2^i-1), the j-th character of X_i is `1` if and only if the binary representation of j with i digits (possibly with leading zeros) belongs to S. Here, the first and last characters in X_i are called the 0-th and (2^i-1)-th characters, respectively.
* S does not contain a string with length N+1 or more.



Here, a string A is a subsequence of another string B when there exists a sequence of integers t_1 < ... < t_{|A|} such that, for every i (1\leq i\leq |A|), the i-th character of A and the t_i-th character of B is equal.

Constraints

* 0 \leq N \leq 20
* X_i(0\leq i\leq N) is a string of length 2^i consisting of `0` and `1`.
* 1 \leq K \leq |S|
* K is an integer.

Input

Input is given from Standard Input in the following format:


N K
X_0
:
X_N


Output

Print the lexicographically smallest string among the longest strings that are subsequences of K or more different strings in S.

Examples

Input

3 4
1
01
1011
01001110


Output

10


Input

4 6
1
01
1011
10111010
1101110011111101


Output

100


Input

2 5
0
11
1111


Output

### Response

```cpp
#include <bits/stdc++.h>
#define ll long long
#define maxn 1100005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
const int r2 = 21; 
struct th {
	vector<vi> s;
	int sum;
	void init(int k) {
		sum = 0;
		s.resize(k + 1);
		for (int i = 0; i <= k; i++) {
			s[i].resize(1 << i);
			for (int j = 0; j < s[i].size(); j++)
				s[i][j] = 0;
		}
	}
	void ch(pi pl, int num) {
		s[pl.fi][pl.se] += num, sum += num;
	}
}nr[1 << r2], sr[1 << r2];

vector<pi> nx[r2][2];
char inp[1 << r2];
int main() {
	for (int i = 0; i < r2; i++)
		for (int k = 0; k < 2; k++) {
			nx[i][k].resize(1 << i);
			for (int j = 0; j < (1 << i); j++) {
				if (i == 0) nx[i][k][j] = mp(-1, 0);
				else {
					int rr = j & (1 << (i - 1));
					if (rr && k) nx[i][k][j] = mp(i - 1, j ^ (1 << (i - 1)));
					else if (rr == 0 && k == 0) nx[i][k][j] = mp(i - 1, j);
					else nx[i][k][j] = nx[i - 1][k][j % (1 << (i - 1))];
				}
			}
		}
	int n, k;
	cin >> n >> k;
	int nl = 0, res = 0;
	nr[0].init(n);
	for (int i = 0; i <= n; i++) {
		scanf("%s", inp);
		for (int j = 0; j < (1 << i); j++)
			if (inp[j] == '1') nr[0].ch(mp(i, j), 1);
	}
	for (int tt = 1; tt <= n; tt++) {
	//	cout << "!!!" << tt << endl;
		for (int m = 0; m < (1 << tt); m++)
			sr[m].init(n - tt);
		for (int m = 0; m < (1 << (tt - 1)); m++)
			for (int s = 0; s <= n - tt + 1; s++)
				for (int q = 0; q < nr[m].s[s].size(); q++)
					for (int r = 0; r < 2; r++)
						if (!nr[m].s[s][q]) continue;
						else {
							pi ed = nx[s][r][q];
							if (ed.fi != -1)
								sr[m * 2 + r].ch(ed, nr[m].s[s][q]);
						}
		for (int m = 0; m < (1 << tt); m++)
			if (sr[m].sum >= k) {
				nl = tt;
				res = m;
				break;
			}
		for (int m = 0; m < (1 << tt); m++)
			nr[m] = sr[m];
	}
	vi otp(nl);
	for (int i = 0; i < nl; i++)
		otp[i] = res % 2, res /= 2;
	for (int i = nl - 1; i >= 0; i--)
		printf("%d", otp[i]);
	printf("\n");
	return 0;
}

```