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 <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=22,M=1<<21;
int n,k;
char s[M];
int dp[N][M],f0[M],f1[M];
int head=0,tail=0;
int Log[1<<N];
int main(){
	n=read(),k=read();
	For(i,2,(1<<N)-1)
		Log[i]=Log[i>>1]+1;
	For(i,0,n){
		scanf("%s",s);
		For(j,0,(1<<i)-1){
			dp[0][j+(1<<i)]=s[j]-'0';
			f0[j+(1<<i)]=f1[j+(1<<i)]=-1;
			For(t,0,i-1)
				if (~j>>t&1){
					f0[j+(1<<i)]=t;
					break;
				}
			For(t,0,i-1)
				if (j>>t&1){
					f1[j+(1<<i)]=t;
					break;
				}
		}
	}
	int ansl=-1,ans=0;
	For(ls,0,n)
		For(s,0,(1<<ls)-1)
			Fod(lt,n-ls,0){	
				int ad=1<<(ls+lt);
				if (lt==0){
					if (dp[ls][s+ad]>=k)
						if (ls>ansl||(ls==ansl&&s<ans))
							ansl=ls,ans=s;
				}
				else {
					For(t,0,(1<<lt)-1){
						int v=dp[ls][(s<<lt|t)+ad];
						if (!v)
							continue;
						dp[ls][s+(1<<ls)]+=v;
						int F0=f0[t+(1<<lt)],F1=f1[t+(1<<lt)];
						if (~F0)
							dp[ls+1][((s|0<<ls)<<(lt-F0-1)|t>>(F0+1))+(1<<(ls+lt-F0))]+=v;
						if (~F1)
							dp[ls+1][((s|1<<ls)<<(lt-F1-1)|t>>(F1+1))+(1<<(ls+lt-F1))]+=v;
					}
				}
			}
	Fod(i,ansl-1,0)
		putchar('0'+(ans>>i&1));
	return 0;
}