#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}int n,k,nxt[2][1<<21],F[21][1<<21],Lg[1<<21],tot;
char s[1<<20];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),k=read();
	Rep(i,0,n){scanf("%s",s);for(int j=0;j<1<<i;j++)if(s[j]==49)F[i][1<<i^j]=1;}
	Lg[0]=-1;for(int i=1;i<2<<n;i++)Lg[i]=Lg[i>>1]+1;
	for(int s=2;s<2<<n;s++){
		if(s>>(Lg[s]-1)&1)nxt[1][s]=s^1<<Lg[s],nxt[0][s]=nxt[0][nxt[1][s]];
		else nxt[0][s]=s^3<<Lg[s]-1,nxt[1][s]=nxt[1][nxt[0][s]];
	}Red(i,n,1)for(int s=1<<i;s<2<<n;s++)if(F[i][s]){
		int A=s>>i,B=(s&((1<<i)-1))^1<<i;
		if(nxt[0][B])F[Lg[nxt[0][B]]][(A<<1^1)<<Lg[nxt[0][B]]^nxt[0][B]]+=F[i][s];
		if(nxt[1][B])F[Lg[nxt[1][B]]][(A<<1^0)<<Lg[nxt[1][B]]^nxt[1][B]]+=F[i][s];
		F[0][A]+=F[i][s];
	}int Ans=1;
	for(int i=2;i<2<<n;i++)if(F[0][i]>=k&&Lg[i]>Lg[Ans])Ans=i;
	int j=n;for(;~Ans>>j&1;j--);for(;j--;)cout<<(Ans>>j&1);
	return 0;
}



### Prompt

Create a solution in Cpp for 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>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}int n,k,nxt[2][1<<21],F[21][1<<21],Lg[1<<21],tot;
char s[1<<20];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),k=read();
	Rep(i,0,n){scanf("%s",s);for(int j=0;j<1<<i;j++)if(s[j]==49)F[i][1<<i^j]=1;}
	Lg[0]=-1;for(int i=1;i<2<<n;i++)Lg[i]=Lg[i>>1]+1;
	for(int s=2;s<2<<n;s++){
		if(s>>(Lg[s]-1)&1)nxt[1][s]=s^1<<Lg[s],nxt[0][s]=nxt[0][nxt[1][s]];
		else nxt[0][s]=s^3<<Lg[s]-1,nxt[1][s]=nxt[1][nxt[0][s]];
	}Red(i,n,1)for(int s=1<<i;s<2<<n;s++)if(F[i][s]){
		int A=s>>i,B=(s&((1<<i)-1))^1<<i;
		if(nxt[0][B])F[Lg[nxt[0][B]]][(A<<1^1)<<Lg[nxt[0][B]]^nxt[0][B]]+=F[i][s];
		if(nxt[1][B])F[Lg[nxt[1][B]]][(A<<1^0)<<Lg[nxt[1][B]]^nxt[1][B]]+=F[i][s];
		F[0][A]+=F[i][s];
	}int Ans=1;
	for(int i=2;i<2<<n;i++)if(F[0][i]>=k&&Lg[i]>Lg[Ans])Ans=i;
	int j=n;for(;~Ans>>j&1;j--);for(;j--;)cout<<(Ans>>j&1);
	return 0;
}



```