#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = ( 1 << 21 ) + 7;
const int MAXL = 22;

int n, K;
char is[MAXN];
int a[MAXN];
int dp[MAXN][MAXL];
int val[MAXN];
int qlg[MAXN];

void init ();
void input ();
void work ();



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
	
	qlg[0] = qlg[1] = 0;
	lp ( i, 2, MAXN ) qlg[i] = qlg[i>>1] + 1;
}

void input ()
{
	// input method
	
	scanf ( "%d%d", &n, &K );
	lpi ( i, 0, n ){
		scanf ( "%s", is );
		lp ( j, 0, ( 1 << i ) ) a[j|(1<<i)] = is[j] == '1';
	}
}

void work ()
{
	// main work
	
	++n;
	int ms = ( 1 << n ) - 1, v, msk;
//	lpi ( i, 1, ms ) cerr << a[i] << " "; cerr << endl;
	lpd ( i, ms>>1, 0 ){
		lpdi ( j, qlg[i], 0 ){
			if ( j == qlg[i] ){
				dp[i][j] = dp[i<<1][j+1] + a[i<<1] + dp[i<<1|1][j+1] + a[i<<1|1];
			}else{
				dp[i][j] = dp[i][j+1];
				v = i;
				msk = v >> ( qlg[i] - j ) << ( qlg[i] - j );
				v ^= msk;
				if ( ! ( v >> ( qlg[i] - j - 1 ) & 1 ) ) v |= 1 << ( qlg[i] - j );
				v |= msk << 1;
				dp[i][j] += dp[v][j+1] + a[v];
			}
		}
	}
	
//	lpi ( i, 1, ms ) { cerr << i << " : "; lpi ( j, 0, qlg[i] ) cerr << dp[i][j] << " "; cerr << endl; }
	
	lpi ( i, 1, ms ) val[i] = dp[i][0] + a[i];
	
	int ans = 1;
	lpi ( i, 1, ms ){
		if ( val[i] >= K ){
			if ( qlg[i] > qlg[ans] ) ans = i;
		}
	}
	
	string str;
	for ( int t = ans; t ^ 1; t >>= 1 ) str += ( t & 1 ) + '0';
	reverse ( str.begin (), str.end () );
	cout << str << endl;
}
### Prompt

Please create a solution in Cpp 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>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = ( 1 << 21 ) + 7;
const int MAXL = 22;

int n, K;
char is[MAXN];
int a[MAXN];
int dp[MAXN][MAXL];
int val[MAXN];
int qlg[MAXN];

void init ();
void input ();
void work ();



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
	
	qlg[0] = qlg[1] = 0;
	lp ( i, 2, MAXN ) qlg[i] = qlg[i>>1] + 1;
}

void input ()
{
	// input method
	
	scanf ( "%d%d", &n, &K );
	lpi ( i, 0, n ){
		scanf ( "%s", is );
		lp ( j, 0, ( 1 << i ) ) a[j|(1<<i)] = is[j] == '1';
	}
}

void work ()
{
	// main work
	
	++n;
	int ms = ( 1 << n ) - 1, v, msk;
//	lpi ( i, 1, ms ) cerr << a[i] << " "; cerr << endl;
	lpd ( i, ms>>1, 0 ){
		lpdi ( j, qlg[i], 0 ){
			if ( j == qlg[i] ){
				dp[i][j] = dp[i<<1][j+1] + a[i<<1] + dp[i<<1|1][j+1] + a[i<<1|1];
			}else{
				dp[i][j] = dp[i][j+1];
				v = i;
				msk = v >> ( qlg[i] - j ) << ( qlg[i] - j );
				v ^= msk;
				if ( ! ( v >> ( qlg[i] - j - 1 ) & 1 ) ) v |= 1 << ( qlg[i] - j );
				v |= msk << 1;
				dp[i][j] += dp[v][j+1] + a[v];
			}
		}
	}
	
//	lpi ( i, 1, ms ) { cerr << i << " : "; lpi ( j, 0, qlg[i] ) cerr << dp[i][j] << " "; cerr << endl; }
	
	lpi ( i, 1, ms ) val[i] = dp[i][0] + a[i];
	
	int ans = 1;
	lpi ( i, 1, ms ){
		if ( val[i] >= K ){
			if ( qlg[i] > qlg[ans] ) ans = i;
		}
	}
	
	string str;
	for ( int t = ans; t ^ 1; t >>= 1 ) str += ( t & 1 ) + '0';
	reverse ( str.begin (), str.end () );
	cout << str << endl;
}
```