#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
bool B(int x,int i){return (x>>i)&1;}
int N,X;
vector<string> S;
int dp[21][1<<21];
int cnt[21][1<<21];
int getnext[21][1<<21][2];
void addfrom(int p,int s,int plen,int slen){
	int v = (p<<slen)|s;
	int n = plen+slen;
	int id = v + (1<<n)-1;

	if(plen==0){
		if(S[slen][s]=='1') dp[plen][id]++;
	}

	int val = dp[plen][id];

	cnt[plen][p] += val;

	if(slen==0){
		return;
	}

	rep(c,2){
		int i = getnext[slen][s][c];
		if(i==slen) continue;
		int np = (p<<1)|c;
		int nplen = plen+1;
		int nslen = slen-(i+1);
		int ns = s & ((1<<nslen)-1);

		int nv = (np<<nslen)|ns;
		int nn = nplen+nslen;
		int nid = nv + (1<<nn)-1;
		dp[nplen][nid] += val;
	}
}
int main(){
	cin>>N>>X;
	S.resize(N+1);
	rep(n,N+1){
		cin>>S[n];
//		S[n] = string(1<<n,'1');
	}
	rep(n,N+1){	//calcgetnext
		rep(b,1<<n){
			rep(c,2){
				getnext[n][b][c] = n;
				rep(i,n){
					if(B(b,n-1-i) == c){
						getnext[n][b][c] = i;
						break;
					}
				}
			}
		}
	}
	rep(plen,N+1){
		for(int n=plen;n<=N;n++){
			rep(b,1<<n){
				int slen = n-plen;
				int p = b>>slen;
				int s = b&((1<<slen)-1);
				addfrom(p,s,plen,slen);
			}
		}
	}
	for(int n=N;n>=0;n--){
		rep(b,1<<n){
			if(cnt[n][b] >= X){
				string s;
				rep(i,n) s += '0'+B(b,n-1-i);
				cout<<s<<endl;
				return 0;
			}
		}
	}
}

### Prompt

Generate 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
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
bool B(int x,int i){return (x>>i)&1;}
int N,X;
vector<string> S;
int dp[21][1<<21];
int cnt[21][1<<21];
int getnext[21][1<<21][2];
void addfrom(int p,int s,int plen,int slen){
	int v = (p<<slen)|s;
	int n = plen+slen;
	int id = v + (1<<n)-1;

	if(plen==0){
		if(S[slen][s]=='1') dp[plen][id]++;
	}

	int val = dp[plen][id];

	cnt[plen][p] += val;

	if(slen==0){
		return;
	}

	rep(c,2){
		int i = getnext[slen][s][c];
		if(i==slen) continue;
		int np = (p<<1)|c;
		int nplen = plen+1;
		int nslen = slen-(i+1);
		int ns = s & ((1<<nslen)-1);

		int nv = (np<<nslen)|ns;
		int nn = nplen+nslen;
		int nid = nv + (1<<nn)-1;
		dp[nplen][nid] += val;
	}
}
int main(){
	cin>>N>>X;
	S.resize(N+1);
	rep(n,N+1){
		cin>>S[n];
//		S[n] = string(1<<n,'1');
	}
	rep(n,N+1){	//calcgetnext
		rep(b,1<<n){
			rep(c,2){
				getnext[n][b][c] = n;
				rep(i,n){
					if(B(b,n-1-i) == c){
						getnext[n][b][c] = i;
						break;
					}
				}
			}
		}
	}
	rep(plen,N+1){
		for(int n=plen;n<=N;n++){
			rep(b,1<<n){
				int slen = n-plen;
				int p = b>>slen;
				int s = b&((1<<slen)-1);
				addfrom(p,s,plen,slen);
			}
		}
	}
	for(int n=N;n>=0;n--){
		rep(b,1<<n){
			if(cnt[n][b] >= X){
				string s;
				rep(i,n) s += '0'+B(b,n-1-i);
				cout<<s<<endl;
				return 0;
			}
		}
	}
}

```