#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=22;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,m,to[1<<(N+5)][2],id[22][1<<20],tt;
pii ans;
vi f[1<<N],new_f[1<<N];
char s[1<<N];

bool cmp(int x,int y,int len) {
	for(int i=0;i<len;i++) {
		int a=(x>>i&1),b=(y>>i&1);
		if(a!=b) return a<b;
	}
	return 0;
}

int main() {
	cin>>n>>m;
	//n=m=20;
	for(int i=0;i<=n;i++)
		for(int j=0;j<(1<<i);j++) id[i][j]=tt++;
	f[0].resize((1<<(n+1))-1);
	for(int i=0;i<=n;i++) {
		scanf("%s",s);
		//for(int j=0;j<(1<<i);j++) s[j]='1';
		for(int j=0;j<(1<<i);j++)
			if(s[j]=='1') {
				int rev=0;
				for(int k=0;k<i;k++) rev|=(j>>k&1)<<(i-k-1);
				++f[0][id[i][rev]];
			}
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<(1<<i);j++) {
			int s=id[i][j];
			for(int k=0;k<2;k++) {
				int p=0;while(p<i&&(j>>p&1)!=k) ++p;
				if(p==i) to[s][k]=-1;
				else to[s][k]=id[i-p-1][j>>(p+1)];
			}
		}
	//exit(0);
	for(int i=0;i<=n;i++) {
		//s的长度为i->i+1
		//cerr<<i<<'\n';
		for(int j=0;j<(1<<N);j++) {
			vi emp;
			new_f[j].swap(emp);
		}
		for(int j=0;j<(1<<(i+1));j++) new_f[j].resize((1<<(n-i))-1);
		//cerr<<i<<'\n';
		for(int j=0;j<(1<<i);j++) {
			int sum=0;
			for(int k=0;k<sz(f[j]);k++) {
				sum+=f[j][k];
			}
			if(sum>=m) {
				if(ans.fi!=i||!cmp(ans.se,j,i)) ans=mp(i,j);
			}
			if(i<n) {
				for(int k=0;k<sz(f[j]);k++) {
					if(!f[j][k]) continue;
					for(int l=0;l<2;l++)
						if(~to[k][l]) {
							new_f[j|(l<<i)][to[k][l]]+=f[j][k];
						}
				}
			}
		}
		swap(f,new_f);
	}
	for(int i=0;i<ans.fi;i++) cout<<(ans.se>>i&1);
	return 0;
}

### Prompt

Please create a solution in cpp 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=22;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,m,to[1<<(N+5)][2],id[22][1<<20],tt;
pii ans;
vi f[1<<N],new_f[1<<N];
char s[1<<N];

bool cmp(int x,int y,int len) {
	for(int i=0;i<len;i++) {
		int a=(x>>i&1),b=(y>>i&1);
		if(a!=b) return a<b;
	}
	return 0;
}

int main() {
	cin>>n>>m;
	//n=m=20;
	for(int i=0;i<=n;i++)
		for(int j=0;j<(1<<i);j++) id[i][j]=tt++;
	f[0].resize((1<<(n+1))-1);
	for(int i=0;i<=n;i++) {
		scanf("%s",s);
		//for(int j=0;j<(1<<i);j++) s[j]='1';
		for(int j=0;j<(1<<i);j++)
			if(s[j]=='1') {
				int rev=0;
				for(int k=0;k<i;k++) rev|=(j>>k&1)<<(i-k-1);
				++f[0][id[i][rev]];
			}
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<(1<<i);j++) {
			int s=id[i][j];
			for(int k=0;k<2;k++) {
				int p=0;while(p<i&&(j>>p&1)!=k) ++p;
				if(p==i) to[s][k]=-1;
				else to[s][k]=id[i-p-1][j>>(p+1)];
			}
		}
	//exit(0);
	for(int i=0;i<=n;i++) {
		//s的长度为i->i+1
		//cerr<<i<<'\n';
		for(int j=0;j<(1<<N);j++) {
			vi emp;
			new_f[j].swap(emp);
		}
		for(int j=0;j<(1<<(i+1));j++) new_f[j].resize((1<<(n-i))-1);
		//cerr<<i<<'\n';
		for(int j=0;j<(1<<i);j++) {
			int sum=0;
			for(int k=0;k<sz(f[j]);k++) {
				sum+=f[j][k];
			}
			if(sum>=m) {
				if(ans.fi!=i||!cmp(ans.se,j,i)) ans=mp(i,j);
			}
			if(i<n) {
				for(int k=0;k<sz(f[j]);k++) {
					if(!f[j][k]) continue;
					for(int l=0;l<2;l++)
						if(~to[k][l]) {
							new_f[j|(l<<i)][to[k][l]]+=f[j][k];
						}
				}
			}
		}
		swap(f,new_f);
	}
	for(int i=0;i<ans.fi;i++) cout<<(ans.se>>i&1);
	return 0;
}

```