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

Solution (in CPP):

Solution:
#include<cstdio>
#include<cstring>
#define fo(x,a,b) for(int x=(a),e_=(b);x<=e_;x++)
#define fd(x,a,b) for(int x=(a),e_=(b);x>=e_;x--)
#define two(x) (1<<(x))

const int N=2097153;
int f[21][N],vis[21][N],tot[N],lg[N],n,m,ans,mx;
char X[N],c[30];

int main(){
	int len,nxt,ful,w,go,dt;
	scanf("%d %d",&n,&m);
	memset(vis,-1,sizeof(vis));
	lg[0]=-1;fo(i,1,N-1) lg[i]=lg[i>>1]+1;
	fo(i,0,n) {
		len=two(i);
		scanf("%s",X);
		fo(j,0,len-1) if(X[j]=='1') vis[i][len+j]=i, f[i][len+j]=1;
//		printf("\nlen:%d\n",len);
		
		fd(z,i,1) {//zero is end state 
			ful=two(z)-1;
			fo(s,0,len+len-1) if(vis[z][s]==i) {
				tot[s>>z]+=f[z][s];
				nxt=s&ful;
//				printf("s:%d[%d] f:%d nxt:%d\n",s,z,f[z][s],nxt);
				if(nxt) {
					w=lg[nxt];
					go=((s>>z)<<(w+1)) | (s&(two(w+1)-1));//change together
					if(vis[w][go]!=i) vis[w][go]=i, f[w][go]=0;
//					printf("trans to %d[%d]\n",go,w);
					f[w][go]+=f[z][s];
				}
				nxt=ful-nxt;
				if(nxt) {
					w=lg[nxt];
					go=((s>>z)<<(w+1)) | (s&(two(w+1)-1));
					if(vis[w][go]!=i) vis[w][go]=i, f[w][go]=0;
//					printf("trans to %d[%d]\n",go,w);
					f[w][go]+=f[z][s];
				}
			}
		}
		fo(s,0,len+len-1) if(vis[0][s]==i) {
//			printf("s:%d[0] f:%d\n",s,f[0][s]);
			tot[s]+=f[0][s];
		}
	}
//	puts("");

	mx=ans=0;
	fd(s,two(n+1)-1,0) {
//		printf("s:%d tot:%d\n",s,tot[s]);
		if(tot[s]>=m && (lg[s]>mx || lg[s]==mx && s<ans)) mx=lg[s], ans=s; 
	}
//	printf("ans:%d\n",ans);

	for(len=0; ans>1; ans=ans>>1) c[++len]=(ans&1)+48;
	for(; len; len--) putchar(c[len]);
	return 0;
}