#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 100010;
const int INF = 2147483600;

int N,K; int hbit[21][(1<<21)]; int *f[21][21];
int sta[MAXN+1],top; char str[(1<<21)]; bool V[21][(1<<20)];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=read(); K=read();
	for(int i=0;i<=N;i++)
		for(int j=0;j<=N&&i+j<=N;j++){
			f[i][j]=new int[(1<<(i+j))];
			for(int k=0;k<(1<<(i+j));k++) f[i][j][k]=0;
		}
	for(int i=0;i<=N;i++){
		scanf("%s",str);
		for(int j=0;j<(1<<i);j++) f[0][i][j]=str[j]-'0',V[i][j]=str[j]-'0';
	} hbit[1][0]=hbit[1][1]=-1;
	for(int i=1;i<N;i++){
		for(int j=0;j<(1<<i);j++){
			for(int k=0;k<2;k++){
				if((((1<<(i-1))&j)>>(i-1))==k) hbit[i+1][j|(k<<i)]=hbit[i][j];
				else hbit[i+1][j|(k<<i)]=i-1;
			}
		}
	}
	for(int i=0;i<=N;i++){
		for(int j=1;j<=N;j++){
			for(int k=0;i+j<=N&&k<(1<<(i+j));k++){
				int ta=(k&(((1<<i)-1)<<j))>>j,tb=k&((1<<j)-1);
				//cout<<i<<" "<<j<<":"<<k<<" | "<<ta<<" "<<tb<<" |"<<f[3][0][0]<<endl;
				f[i][0][ta]+=f[i][j][k];
				if(i==N) continue;
				//cout<<"ed1\n";
				for(int c=0;c<2;c++){
					int pos=-1;
					if(((k&(1<<(j-1)))>>(j-1))==c) pos=j-1;
					else pos=hbit[j][k&((1<<j)-1)];
					if(pos==-1) continue;
					int tnsa=ta,tnsb=tb;
					tnsa<<=1; tnsa|=c;
					tnsb&=((1<<pos)-1);
					//cout<<"res:"<<tnsa<<" "<<tnsb<<endl;
					f[i+1][pos][(tnsa<<pos)|tnsb]+=f[i][j][k];
					//cout<<"pp:"<<i+1<<" "<<pos<<endl;
				} //cout<<"ed\n";
			}
		}
	} for(int i=N;i>=0;i--){
		for(int j=0;j<(1<<i);j++){
			if(f[i][0][j]>=K){
				int x=j; while(x){ sta[++top]=(x&1); x>>=1; }
				while(top<i) sta[++top]=0;
				for(int i=top;i>=1;i--) printf("%d",sta[i]);
				return 0;
			}
		}
	} 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<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 100010;
const int INF = 2147483600;

int N,K; int hbit[21][(1<<21)]; int *f[21][21];
int sta[MAXN+1],top; char str[(1<<21)]; bool V[21][(1<<20)];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=read(); K=read();
	for(int i=0;i<=N;i++)
		for(int j=0;j<=N&&i+j<=N;j++){
			f[i][j]=new int[(1<<(i+j))];
			for(int k=0;k<(1<<(i+j));k++) f[i][j][k]=0;
		}
	for(int i=0;i<=N;i++){
		scanf("%s",str);
		for(int j=0;j<(1<<i);j++) f[0][i][j]=str[j]-'0',V[i][j]=str[j]-'0';
	} hbit[1][0]=hbit[1][1]=-1;
	for(int i=1;i<N;i++){
		for(int j=0;j<(1<<i);j++){
			for(int k=0;k<2;k++){
				if((((1<<(i-1))&j)>>(i-1))==k) hbit[i+1][j|(k<<i)]=hbit[i][j];
				else hbit[i+1][j|(k<<i)]=i-1;
			}
		}
	}
	for(int i=0;i<=N;i++){
		for(int j=1;j<=N;j++){
			for(int k=0;i+j<=N&&k<(1<<(i+j));k++){
				int ta=(k&(((1<<i)-1)<<j))>>j,tb=k&((1<<j)-1);
				//cout<<i<<" "<<j<<":"<<k<<" | "<<ta<<" "<<tb<<" |"<<f[3][0][0]<<endl;
				f[i][0][ta]+=f[i][j][k];
				if(i==N) continue;
				//cout<<"ed1\n";
				for(int c=0;c<2;c++){
					int pos=-1;
					if(((k&(1<<(j-1)))>>(j-1))==c) pos=j-1;
					else pos=hbit[j][k&((1<<j)-1)];
					if(pos==-1) continue;
					int tnsa=ta,tnsb=tb;
					tnsa<<=1; tnsa|=c;
					tnsb&=((1<<pos)-1);
					//cout<<"res:"<<tnsa<<" "<<tnsb<<endl;
					f[i+1][pos][(tnsa<<pos)|tnsb]+=f[i][j][k];
					//cout<<"pp:"<<i+1<<" "<<pos<<endl;
				} //cout<<"ed\n";
			}
		}
	} for(int i=N;i>=0;i--){
		for(int j=0;j<(1<<i);j++){
			if(f[i][0][j]>=K){
				int x=j; while(x){ sta[++top]=(x&1); x>>=1; }
				while(top<i) sta[++top]=0;
				for(int i=top;i>=1;i--) printf("%d",sta[i]);
				return 0;
			}
		}
	} return 0;
}



```