#include <cstdio>

int ch[2][1<<22], id[22][1<<21], cnt;
void get() {
	id[0][0] = (cnt++), ch[0][id[0][0]] = ch[1][id[0][0]] = -1;
	for(int i=1;i<=20;i++) {
		int t = (1 << i), k = (t >> 1);
		for(int s=0;s<t;s++) {
			id[i][s] = (cnt++);
			int p = (s & k), q = (p ? 1 : 0);
			ch[q][id[i][s]] = id[i-1][s^p];
			ch[!q][id[i][s]] = ch[!q][id[i-1][s^p]];
		}
	}
}

int a[22][1<<22], siz[22], c[22][1<<22], num[22][1<<22];

int ans[22], N, K;
void dfs(int d, int s) {
	if( ans[d] == -1 ) ans[d] = s;
	for(int p=0;p<=1;p++) {
		int tot = 0;
		for(int i=0;i<siz[d];i++) {
			int to = ch[p][a[d][i]];
			if( to == -1 ) continue;
			if( num[d + 1][to] == -1 )
				num[d + 1][a[d + 1][siz[d + 1]] = to] = siz[d + 1], siz[d + 1]++;
			tot += c[d][i], c[d + 1][num[d + 1][to]] += c[d][i];
		}
		if( tot >= K ) dfs(d + 1, (s << 1) | p);
		for(int i=0;i<siz[d + 1];i++)
			num[d + 1][a[d + 1][i]] = -1, c[d + 1][i] = 0;
		siz[d + 1] = 0;
	}
}

char s[1<<21];
int main() {
	scanf("%d%d", &N, &K), get();
	for(int i=0;i<=N;i++)
		for(int j=0;j<cnt;j++)
			num[i][j] = -1;
	for(int i=0;i<=N;i++) {
		scanf("%s", s);
		int t = (1 << i);
		for(int j=0;j<t;j++) {
			if( s[j] == '1' )
				num[0][a[0][siz[0]] = id[i][j]] = siz[0], c[0][num[0][id[i][j]]]++, siz[0]++;
		}
		ans[i] = -1;
	}
	dfs(0, 0);
	for(int i=N;i>=0;i--) {
		if( ans[i] != -1 ) {
			for(int j=i-1;j>=0;j--)
				putchar(((ans[i] >> j) & 1) + '0');
			puts(""); return 0;
		}
	}
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <cstdio>

int ch[2][1<<22], id[22][1<<21], cnt;
void get() {
	id[0][0] = (cnt++), ch[0][id[0][0]] = ch[1][id[0][0]] = -1;
	for(int i=1;i<=20;i++) {
		int t = (1 << i), k = (t >> 1);
		for(int s=0;s<t;s++) {
			id[i][s] = (cnt++);
			int p = (s & k), q = (p ? 1 : 0);
			ch[q][id[i][s]] = id[i-1][s^p];
			ch[!q][id[i][s]] = ch[!q][id[i-1][s^p]];
		}
	}
}

int a[22][1<<22], siz[22], c[22][1<<22], num[22][1<<22];

int ans[22], N, K;
void dfs(int d, int s) {
	if( ans[d] == -1 ) ans[d] = s;
	for(int p=0;p<=1;p++) {
		int tot = 0;
		for(int i=0;i<siz[d];i++) {
			int to = ch[p][a[d][i]];
			if( to == -1 ) continue;
			if( num[d + 1][to] == -1 )
				num[d + 1][a[d + 1][siz[d + 1]] = to] = siz[d + 1], siz[d + 1]++;
			tot += c[d][i], c[d + 1][num[d + 1][to]] += c[d][i];
		}
		if( tot >= K ) dfs(d + 1, (s << 1) | p);
		for(int i=0;i<siz[d + 1];i++)
			num[d + 1][a[d + 1][i]] = -1, c[d + 1][i] = 0;
		siz[d + 1] = 0;
	}
}

char s[1<<21];
int main() {
	scanf("%d%d", &N, &K), get();
	for(int i=0;i<=N;i++)
		for(int j=0;j<cnt;j++)
			num[i][j] = -1;
	for(int i=0;i<=N;i++) {
		scanf("%s", s);
		int t = (1 << i);
		for(int j=0;j<t;j++) {
			if( s[j] == '1' )
				num[0][a[0][siz[0]] = id[i][j]] = siz[0], c[0][num[0][id[i][j]]]++, siz[0]++;
		}
		ans[i] = -1;
	}
	dfs(0, 0);
	for(int i=N;i>=0;i--) {
		if( ans[i] != -1 ) {
			for(int j=i-1;j>=0;j--)
				putchar(((ans[i] >> j) & 1) + '0');
			puts(""); return 0;
		}
	}
}
```