#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

#define bit(x) (1<<(x))
int dp[(1<<21)+10][4],pd[(1<<21)+10][4],ret[(1<<21)+10];
int n,k;
char s[(1<<21)+10];
void gao(int x) {
	int m=bit(x);
	rep(i,0,bit(x+1)) rep(ban,0,4) dp[i][ban]=0;
	rep(i,0,m) dp[i+m][0]=s[i]=='1';
	per(k,1,x+1) {
		rep(i,0,bit(x+1)) rep(ban,0,4) pd[i][ban]=dp[i][ban],dp[i][ban]=0;
		rep(i,0,bit(x+1)) rep(ban,0,4) {
			int pl=i>>k,pm=(i>>(k-1))&1,pr=i&(bit(k-1)-1);
//			printf("%d ban: %d pl:%d pr: %d %d\n",k,ban,pl,i&(bit(k)-1),pd[i][ban]);
			dp[(pl<<(k-1))+pr][ban|(1<<pm)]+=pd[i][ban];
			if ((ban&bit(pm))==0) {
				dp[((pl*2+pm)<<(k-1))+pr][0]+=pd[i][ban];
			}
		}
	}
//	puts("-------");
	rep(i,0,bit(x+1)) rep(ban,0,4) ret[i]+=dp[i][ban];
}
int main() {
	scanf("%d%d",&n,&k);
	rep(i,0,n+1) {
		scanf("%s",s);
		if (i==0) continue;
		gao(i);
	}
/*	rep(S,1,bit(n+1)) {
		printf("%d %d\n",S,ret[S]);
	}*/
	per(i,1,n+1) rep(sl,bit(i),bit(i)+bit(i)) if (ret[sl]>=k) {
		per(j,0,i) printf("%d",(sl>>j)&1);
		puts("");
		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>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

#define bit(x) (1<<(x))
int dp[(1<<21)+10][4],pd[(1<<21)+10][4],ret[(1<<21)+10];
int n,k;
char s[(1<<21)+10];
void gao(int x) {
	int m=bit(x);
	rep(i,0,bit(x+1)) rep(ban,0,4) dp[i][ban]=0;
	rep(i,0,m) dp[i+m][0]=s[i]=='1';
	per(k,1,x+1) {
		rep(i,0,bit(x+1)) rep(ban,0,4) pd[i][ban]=dp[i][ban],dp[i][ban]=0;
		rep(i,0,bit(x+1)) rep(ban,0,4) {
			int pl=i>>k,pm=(i>>(k-1))&1,pr=i&(bit(k-1)-1);
//			printf("%d ban: %d pl:%d pr: %d %d\n",k,ban,pl,i&(bit(k)-1),pd[i][ban]);
			dp[(pl<<(k-1))+pr][ban|(1<<pm)]+=pd[i][ban];
			if ((ban&bit(pm))==0) {
				dp[((pl*2+pm)<<(k-1))+pr][0]+=pd[i][ban];
			}
		}
	}
//	puts("-------");
	rep(i,0,bit(x+1)) rep(ban,0,4) ret[i]+=dp[i][ban];
}
int main() {
	scanf("%d%d",&n,&k);
	rep(i,0,n+1) {
		scanf("%s",s);
		if (i==0) continue;
		gao(i);
	}
/*	rep(S,1,bit(n+1)) {
		printf("%d %d\n",S,ret[S]);
	}*/
	per(i,1,n+1) rep(sl,bit(i),bit(i)+bit(i)) if (ret[sl]>=k) {
		per(j,0,i) printf("%d",(sl>>j)&1);
		puts("");
		return 0;
	}
}

```