#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<set>
#include<cmath>
#include<vector>

using namespace std;

#define bomb exit(1)
#define INF 1000000000
#define LINF 1000000000000000000ll
#define pprint(x) print(x),putchar(' ')
#define fprint(x) print(x),putchar('\n')
#define EE(x); struct edge { int nxt,to,w; }e[M << 1]; int head[N],cnt = x ^ 1;\
	void add(int u,int v,int w = 0) { e[++cnt].w = w,e[cnt].to = v,e[cnt].nxt = head[u];head[u] = cnt; }\
	void add_edge(int u,int v,int w = 0) { add(u,v,w),add(v,u,w * x); }
#define Mod(x) ((x) >= mod ? x - mod : x)
#define eps 0.0000000001
#define sqr(x) ((x) * (x))
#define iter iterator
#define fi first
#define se second
#define ll long long
//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
//char BB[1 << 15],*SS = BB,*TT = BB;
inline ll read()
{
	ll x = 0;int f = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
	for(;isdigit(ch);ch = getchar()) x = x * 10 + (ch ^ 48);
	return x * f;
}
void print(ll x)
{
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

const int N = 21;

int n,k,s[1 << N],tr[1 << N][2];
int f[N][1 << N],ans;

int main() {
	n = read(),k = read();
	for(int i = 0;i <= n;i++)
		for(int x = 0;x < 1 << i;x++)
			scanf("%1d",&f[i][1 << i ^ x]);
	s[0] = -1;
	for(int i = 1;i < 2 << n;i++) s[i] = s[i >> 1] + 1;
	for(int i = 2;i < 2 << n;++i)
		if(i >> (s[i] - 1) & 1)
		{
			tr[i][1] = i ^ 1 << s[i];
			tr[i][0] = tr[tr[i][1]][0];
		}
		else
		{
			tr[i][0] = i ^ 3 << (s[i] - 1);
			tr[i][1] = tr[tr[i][0]][1];
		}
	for(int i = n;i >= 1;--i)
		for(int j = 1 << i;j < 2 << n;++j) if(f[i][j])
		{
			int p = j >> i,now = (j & ((1 << i) - 1)) ^ 1 << i;
			if(tr[now][0]) f[s[tr[now][0]]][(p << 1 ^ 1) << s[tr[now][0]] ^ tr[now][0]] += f[i][j];
			if(tr[now][1]) f[s[tr[now][1]]][(p << 1 ^ 0) << s[tr[now][1]] ^ tr[now][1]] += f[i][j];
			f[0][p] += f[i][j];
		}
	ans = 1;
	for(int i = 2;i < 2 << n;i++) if(f[0][i] >= k && s[i] > s[ans]) ans = i;
	int j = n;
	while(~ans >> j & 1) j--;
	while(j--) print(ans >> j & 1);
	return 0;
}
### Prompt

Your task is to create a cpp solution to 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<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<set>
#include<cmath>
#include<vector>

using namespace std;

#define bomb exit(1)
#define INF 1000000000
#define LINF 1000000000000000000ll
#define pprint(x) print(x),putchar(' ')
#define fprint(x) print(x),putchar('\n')
#define EE(x); struct edge { int nxt,to,w; }e[M << 1]; int head[N],cnt = x ^ 1;\
	void add(int u,int v,int w = 0) { e[++cnt].w = w,e[cnt].to = v,e[cnt].nxt = head[u];head[u] = cnt; }\
	void add_edge(int u,int v,int w = 0) { add(u,v,w),add(v,u,w * x); }
#define Mod(x) ((x) >= mod ? x - mod : x)
#define eps 0.0000000001
#define sqr(x) ((x) * (x))
#define iter iterator
#define fi first
#define se second
#define ll long long
//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
//char BB[1 << 15],*SS = BB,*TT = BB;
inline ll read()
{
	ll x = 0;int f = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
	for(;isdigit(ch);ch = getchar()) x = x * 10 + (ch ^ 48);
	return x * f;
}
void print(ll x)
{
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

const int N = 21;

int n,k,s[1 << N],tr[1 << N][2];
int f[N][1 << N],ans;

int main() {
	n = read(),k = read();
	for(int i = 0;i <= n;i++)
		for(int x = 0;x < 1 << i;x++)
			scanf("%1d",&f[i][1 << i ^ x]);
	s[0] = -1;
	for(int i = 1;i < 2 << n;i++) s[i] = s[i >> 1] + 1;
	for(int i = 2;i < 2 << n;++i)
		if(i >> (s[i] - 1) & 1)
		{
			tr[i][1] = i ^ 1 << s[i];
			tr[i][0] = tr[tr[i][1]][0];
		}
		else
		{
			tr[i][0] = i ^ 3 << (s[i] - 1);
			tr[i][1] = tr[tr[i][0]][1];
		}
	for(int i = n;i >= 1;--i)
		for(int j = 1 << i;j < 2 << n;++j) if(f[i][j])
		{
			int p = j >> i,now = (j & ((1 << i) - 1)) ^ 1 << i;
			if(tr[now][0]) f[s[tr[now][0]]][(p << 1 ^ 1) << s[tr[now][0]] ^ tr[now][0]] += f[i][j];
			if(tr[now][1]) f[s[tr[now][1]]][(p << 1 ^ 0) << s[tr[now][1]] ^ tr[now][1]] += f[i][j];
			f[0][p] += f[i][j];
		}
	ans = 1;
	for(int i = 2;i < 2 << n;i++) if(f[0][i] >= k && s[i] > s[ans]) ans = i;
	int j = n;
	while(~ans >> j & 1) j--;
	while(j--) print(ans >> j & 1);
	return 0;
}
```