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 mp make_pair
#define pb push_back
#define ph push
#define ptc putchar
#define enter putchar('\n')
#define mod 998244353
using namespace std;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef long long lnt;
typedef unsigned long long ull;
inline int read(){
	int x = 0;char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + c - '0' , c = getchar();
	return x;
}
inline void write(int x){
	if (!x){
       ptc('0');
       return;
	}
	int dg[20] , len = 0;
	while (x) dg[len++] = x % 10 , x /= 10;
	while (len--) ptc(dg[len]+'0');
}
inline void writeln(int x){
	write(x);
	ptc('\n');
}
inline int add(int x,int y){
	x += y;if (x >= mod) x -= mod;
	return x;
}
inline int sub(int x,int y){
	x -= y;if (x < 0) x += mod;
	return x;
}
inline int qpow(int x,int y){
	int res = 1;
	while (y){
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;y >>= 1;
	}
	return res;
}

const int N = 20;


int nodecnt = 0;
int n , lim;
int f[N + 1][1 << N] ;
int last[2] , nxt[N + 1][1 << N][2];

 
int main(){
	scanf("%d%d",&n,&lim);
//	n = 20;lim= 0;
	
	for (int i = 0;i <= n;i++){
		for (int j = 0;j < 1 << i;j++){
			char c = getchar();while (c != '0' && c != '1') c = getchar();
			f[i][j] = c - '0'; 
		}
	}
	
	memset(nxt , -1 , sizeof nxt);
	
	for (int mask = 0;mask < 1 << n;mask++){
		memset(last , -1 , sizeof last);
		int state = 0;
		for (int i = 1;i <= n;i++){
			last[(mask >> (i - 1)) & 1]	= i;
			
			for (int d = 0;d < 2;d++){
				nxt[i][mask][d] = last[d];
//				printf("pos %d Mask %d d %d %d\n",i,mask,d,last[d]);
			}
		}
	}
	
	
	for (int i = 0;i <= n;i++){
		
		for (int j = 1;i + j <= n;j++){
			for (int k = 0;k < 1 << (i + j);k++)
			if (f[i + j][k]){
				for (int d = 0;d < 2;d++){
					if (nxt[j][k][d] != -1){
						int Nxt = nxt[j][k][d];
						if (Nxt == j) continue; 
//						printf("%d %d %d %d\n",i,j,k,Nxt);
						f[i + Nxt][((k >> j) << Nxt) + (k & ((1 << Nxt) - 1))] += f[i + j][k];
					}
				}
				f[i][k >> j] += f[i + j][k]; 
			}
		}
		
		
	}
	
	
	for (int i = n;i >= 0;i--){
		for (int mask = 0;mask < 1 << i;mask++){
//			printf("%d %d %d\n",i,mask,f[i][mask]);
			if (f[i][mask] >= lim){
				for (int d = i;d >= 1;d--) printf("%d",(mask>>(d-1))&1);
				return 0;
			}
		}
	}
	
	
	return 0;
}