#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in int read()
	{
		int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=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),Bi++;return x*ny;
	}
	in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
	in void flush() {if(C>1<<22) ot();}
	template <typename T>
	in void write(T x,char t)
	{
		int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
	}
	in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=21;
int n,k,c[1<<N],ch[1<<N][2],f[N][1<<N],ans=1;
int main()
{
	n=read(),k=read();char nc=0;
	for(int i=0;i<=n;i++)
	{
		for(int x=0;x<1<<i;x++) {while(nc<48||nc>57)nc=gc();f[i][1<<i^x]=nc^48;nc=0;}
	}
	c[0]=-1;for(int i=1;i<2<<n;i++) c[i]=c[i>>1]+1;
	for(int s=2;s<2<<n;s++)
	if(s>>(c[s]-1)&1) ch[s][1]=s^1<<c[s],ch[s][0]=ch[ch[s][1]][0];
	else ch[s][0]=s^3<<(c[s]-1),ch[s][1]=ch[ch[s][0]][1];
	for(int i=n;i;i--) for(int s=1<<i;s<2<<n;s++) if(f[i][s])
	{
		int b=s>>i,t=(s&((1<<i)-1))^1<<i;
		if(ch[t][0]) f[c[ch[t][0]]][(b<<1^1)<<c[ch[t][0]]^ch[t][0]]+=f[i][s];
		if(ch[t][1]) f[c[ch[t][1]]][(b<<1^0)<<c[ch[t][1]]^ch[t][1]]+=f[i][s];
		f[0][b]+=f[i][s];
	}
	for(int s=2;s<2<<n;s++) if(f[0][s]>=k&&c[s]>c[ans]) ans=s;
	int j=n; while(~ans>>j&1) j--;
	while(j--) sr[++C]=(ans>>j&1)+48;
	return ot(),0;
}
//Author: disangan233
### 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
#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in int read()
	{
		int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=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),Bi++;return x*ny;
	}
	in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
	in void flush() {if(C>1<<22) ot();}
	template <typename T>
	in void write(T x,char t)
	{
		int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
	}
	in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=21;
int n,k,c[1<<N],ch[1<<N][2],f[N][1<<N],ans=1;
int main()
{
	n=read(),k=read();char nc=0;
	for(int i=0;i<=n;i++)
	{
		for(int x=0;x<1<<i;x++) {while(nc<48||nc>57)nc=gc();f[i][1<<i^x]=nc^48;nc=0;}
	}
	c[0]=-1;for(int i=1;i<2<<n;i++) c[i]=c[i>>1]+1;
	for(int s=2;s<2<<n;s++)
	if(s>>(c[s]-1)&1) ch[s][1]=s^1<<c[s],ch[s][0]=ch[ch[s][1]][0];
	else ch[s][0]=s^3<<(c[s]-1),ch[s][1]=ch[ch[s][0]][1];
	for(int i=n;i;i--) for(int s=1<<i;s<2<<n;s++) if(f[i][s])
	{
		int b=s>>i,t=(s&((1<<i)-1))^1<<i;
		if(ch[t][0]) f[c[ch[t][0]]][(b<<1^1)<<c[ch[t][0]]^ch[t][0]]+=f[i][s];
		if(ch[t][1]) f[c[ch[t][1]]][(b<<1^0)<<c[ch[t][1]]^ch[t][1]]+=f[i][s];
		f[0][b]+=f[i][s];
	}
	for(int s=2;s<2<<n;s++) if(f[0][s]>=k&&c[s]>c[ans]) ans=s;
	int j=n; while(~ans>>j&1) j--;
	while(j--) sr[++C]=(ans>>j&1)+48;
	return ot(),0;
}
//Author: disangan233
```