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>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int dp[(1<<20)][21];
int go[(1<<20)][21];
int n,k;
int main(){
	cin>>n>>k;
	for(int i=0;i<=n;i++){
		string s; cin>>s;
		for(int j=0;j<(1<<i);j++){
			if(s[j] == '1'){
				dp[j][i]++;
			}
		}
	}
	//x -> x*
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<(1<<i);j++){
			dp[j][i] += dp[j*2+0][i+1]+dp[j*2+1][i+1];
			//cout<<j<<" "<<i<<" "<<dp[j][i]<<endl;
		}
	}
	for(int a=1;a<=n;a++){
		for(int j=0;j<(1<<n);j++){
			int hoge = j%(1<<a);
			int x = 1-(((j>>(a-1))&1));
			x *= (1<<a);
			go[j][a] = (j-hoge)*2+hoge+x;
		}
	}
	//1->(0...0)1 & 0->(1...1)0
	for(int a=1;a<=n-1;a++){
		for(int i=n-1;i>=a;i--){
			for(int j=0;j<(1<<i);j++){
				dp[j][i] += dp[go[j][a]][i+1];
			}
		}
	}
	for(int a=n;a>=1;a--){
		for(int i=0;i<(1<<a);i++){
			if(dp[i][a] >= k){
				string ret = "";
				rep(x,a){
					ret.pb('0'+i%2);
					i/=2;
				}
				reverse(ret.begin(),ret.end());
				cout<<ret<<endl;
				return 0;
			}
		}
	}
}