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 <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define spln(i,n) (i==n?'\n':' ')
using namespace std;
int n,m,i,j,k,dp[2][22][1<<20],nxt[22][1<<20][2],x;
int main()
{
	scanf("%d%d",&n,&m);
	x=0;
	fz0g(i,n){
		scanf(" ");
		fz0k(j,(1<<i)){
			char c;
			scanf("%c",&c);
			if(c=='1'){
				dp[x][i][j]=1;
			}
		}
	}
	fz1(i,n){
		fz0k(j,(1<<i)){
			nxt[i][j][0]=nxt[i][j][1]=-1;
			fz0k(k,i){
				if((j>>k)&1) nxt[i][j][1]=k; else nxt[i][j][0]=k;
			}
		}
	}
	int len=0,ans=0;
	fz0k(i,n){
		fz1(j,n-i){
			fz0k(k,(1<<(i+j)))if(dp[x][i+j][k]){
				int t=nxt[j][k&((1<<j)-1)][0];
				if(t!=-1){
					dp[x^1][i+t+1][((k>>j)<<(t+1))|(k&((1<<(t+1))-1))]+=dp[x][i+j][k];
				}
				t=nxt[j][k&((1<<j)-1)][1];
				if(t!=-1){
					dp[x^1][i+t+1][((k>>j)<<(t+1))|(k&((1<<(t+1))-1))]+=dp[x][i+j][k];
				}
			}
		}
		memset(dp[x],0,sizeof(dp[x]));
		x^=1;
		fz1(j,n-i-1){
			fz0k(k,(1<<(i+j+1))){
				dp[x][i+1][k>>j]+=dp[x][i+j+1][k];
			}
		}
		for(k=(1<<(i+1))-1;k>=0;k--){
			if(dp[x][i+1][k]>=m){
				len=i+1;
				ans=k;
			}
		}
	}
	fd0k(i,len) putchar('0'|((ans>>i)&1));puts("");
	return 0;
}