#include <bits/stdc++.h>

const int N = 21;

int n, m;
int f[N][1 << N], len[1 << N];
int trans[1 << N][2];
// f[k][S|T]: 已经匹配 S，还需要添加的内容 T' 是 T 的子序列, |T| = k, |S| + '1' + |T| = N + 1, 状态数 O(n*2^n)
inline char nc()
{
	static char buf[1000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)? EOF : *p1++;
}

inline int read()
{
	int neg = 1, res = 0;
	char ch;
	do 
	{
		ch = nc();
		if (ch == '-') neg = -1;
	} while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
	return res * neg;
}

inline int read_bit()
{
	char ch;
	do ch = nc(); while (ch != 48 && ch != 49);
	return ch - 48;
}

int main()
{
	n = read(), m = read();
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j < (1 << i); ++j)
		{
			f[i][1 << i | j] = read_bit();
		}
	}
	len[0] = -1;
	for (int i = 1; i <= 1 << (n + 1); ++i) len[i] = len[i >> 1] + 1;

	for (int S = 2; S <= 1 << (n + 1); ++S)
	{
		if (S >> (len[S] - 1) & 1)
		{
			trans[S][1] = S ^ (1 << len[S]); // 由于形如 1 + T，因此消掉前缀1即可
			trans[S][0] = trans[trans[S][1]][0];
		}
		else
		{
			trans[S][0] = S ^ (3 << (len[S] - 1)); // 消掉前缀 1 同时补一个前缀
			trans[S][1] = trans[trans[S][0]][1];
		}
	}

	for (int i = n; i >= 1; --i)
	{
		for (int S = 1 << i; S < (1 << (n + 1)); ++S)
		{	// S: [A|B]
			if (f[i][S])
			{
				int A = S >> i, B = (S & (1 << i) - 1) | 1 << i, T = 0;
				if (T = trans[B][0]) f[len[T]][(A << 1 | 1) << len[T] ^ T] += f[i][S];
				if (T = trans[B][1]) f[len[T]][(A << 1 | 0) << len[T] ^ T] += f[i][S];
				f[0][A] += f[i][S];
			}
		}
	}
	int ans = 1;
	for (int S = 2; S < 1 << (n + 1); ++S) if (f[0][S] >= m && len[S] > len[ans]) ans = S;
//	for (int i = 0; i <= n; ++i) for (int j = 0; j < 1 << n + 1; ++j) if (f[i][j]) printf("f[%d][%d] = %d\n", i, j, f[i][j]);
//	printf("ans = %d\n", ans);
	int j = n;
	while (~ans >> j & 1) --j;
	while (j--) printf("%d", ans >> j & 1);
	putchar('\n');
//	for (int i = 0; i <= n; ++i) for (int j = 0; j < (1 << N); ++j) if (f[i][j]) printf("state (%d, %d)\n", i, j);
	
	return 0;
}
### Prompt

In CPP, your task is to solve the following problem:

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>

const int N = 21;

int n, m;
int f[N][1 << N], len[1 << N];
int trans[1 << N][2];
// f[k][S|T]: 已经匹配 S，还需要添加的内容 T' 是 T 的子序列, |T| = k, |S| + '1' + |T| = N + 1, 状态数 O(n*2^n)
inline char nc()
{
	static char buf[1000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)? EOF : *p1++;
}

inline int read()
{
	int neg = 1, res = 0;
	char ch;
	do 
	{
		ch = nc();
		if (ch == '-') neg = -1;
	} while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
	return res * neg;
}

inline int read_bit()
{
	char ch;
	do ch = nc(); while (ch != 48 && ch != 49);
	return ch - 48;
}

int main()
{
	n = read(), m = read();
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j < (1 << i); ++j)
		{
			f[i][1 << i | j] = read_bit();
		}
	}
	len[0] = -1;
	for (int i = 1; i <= 1 << (n + 1); ++i) len[i] = len[i >> 1] + 1;

	for (int S = 2; S <= 1 << (n + 1); ++S)
	{
		if (S >> (len[S] - 1) & 1)
		{
			trans[S][1] = S ^ (1 << len[S]); // 由于形如 1 + T，因此消掉前缀1即可
			trans[S][0] = trans[trans[S][1]][0];
		}
		else
		{
			trans[S][0] = S ^ (3 << (len[S] - 1)); // 消掉前缀 1 同时补一个前缀
			trans[S][1] = trans[trans[S][0]][1];
		}
	}

	for (int i = n; i >= 1; --i)
	{
		for (int S = 1 << i; S < (1 << (n + 1)); ++S)
		{	// S: [A|B]
			if (f[i][S])
			{
				int A = S >> i, B = (S & (1 << i) - 1) | 1 << i, T = 0;
				if (T = trans[B][0]) f[len[T]][(A << 1 | 1) << len[T] ^ T] += f[i][S];
				if (T = trans[B][1]) f[len[T]][(A << 1 | 0) << len[T] ^ T] += f[i][S];
				f[0][A] += f[i][S];
			}
		}
	}
	int ans = 1;
	for (int S = 2; S < 1 << (n + 1); ++S) if (f[0][S] >= m && len[S] > len[ans]) ans = S;
//	for (int i = 0; i <= n; ++i) for (int j = 0; j < 1 << n + 1; ++j) if (f[i][j]) printf("f[%d][%d] = %d\n", i, j, f[i][j]);
//	printf("ans = %d\n", ans);
	int j = n;
	while (~ans >> j & 1) --j;
	while (j--) printf("%d", ans >> j & 1);
	putchar('\n');
//	for (int i = 0; i <= n; ++i) for (int j = 0; j < (1 << N); ++j) if (f[i][j]) printf("state (%d, %d)\n", i, j);
	
	return 0;
}
```