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>

#define bit(x) (1 << (x))
#define For(i, j, k) for (int i = j; i <= k; i++)
#define Forr(i, j, k) for (int i = j; i >= k; i--)

const int N = 21;

int buffer[1 << N][N];
int n, k;

int& dp(int l, int ls, int r, int rs) {
	return buffer[bit(l + r) | (ls << r) | rs][r];
}

char S[1 << N];

int main() {

	scanf("%d%d", &n, &k);
	For(i, 0, n) {
		scanf("%s", S);
		For(j, 0, bit(i) - 1) if (S[j] == '1') 
			dp(0, 0, i, j) = 1;
	}

	Forr(r, n, 1) For(rs, 0, bit(r) - 1) {	
		int p1 = -1, p0 = -1;
		Forr(i, r - 1, 0) if (rs & bit(i)) { p1 = i; break; }
		Forr(i, r - 1, 0) if (!(rs & bit(i))) { p0 = i; break; }

		For(l, 0, n - r) For(ls, 0, bit(l) - 1) {
			int w = dp(l, ls, r, rs);
			if (!w) continue;
			if (p1 != -1) dp(l + 1, ls << 1 | 1, p1, rs & (bit(p1) - 1)) += w;
			if (p0 != -1) dp(l + 1, ls << 1, p0, rs & (bit(p0) - 1)) += w;
			dp(l, ls, 0, 0) += w;
		}
	}

	Forr(l, n, 0) For(st, 0, bit(l) - 1)
		if (dp(l, st, 0, 0) >= k) {
			Forr(j, l - 1, 0) putchar(st & bit(j) ? '1' : '0'); 
			puts("");
			return 0;
		}

	return 0;
}