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<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

inline int SH(int x) { return 1<<x; }
inline int BITS(int x) { return (1<<x)-1; }

int N, K;
char buf[(1<<20)+10];
int C[1<<21][21];

void MAIN() {
    scanf("%d%d", &N, &K);
    REP (t, N+1) {
	scanf("%s", buf);
	REP (i, SH(t)) if (buf[i] == '1') {
	    C[i | SH(t)][0]++;
	}
    }

    for (int t=N; t>=0; t--) REP (s, SH(t)) REP (i, t) if (C[s|SH(t)][i]) {
	int cur = C[s|SH(t)][i];
	int sub = s & BITS(i);

	// cut;
	C[sub|SH(i)][i] += cur;

	// 0;
	for (int k=i; k<t; k++) if (~s>>k&1) {
	    int hi = (s>>k)<<i;
	    C[hi|sub|SH(t-k+i)][i+1] += cur;
	    break;
	}

	// 1;
	for (int k=i; k<t; k++) if (s>>k&1) {
	    int hi = (s>>k)<<i;
	    C[hi|sub|SH(t-k+i)][i+1] += cur;
	    break;
	}
    }

    for (int t=N; t>=0; t--) REP (s, SH(t)) if (C[s|SH(t)][t] >= K) {
	for (int i=t; i--;) buf[t-1-i] = (s>>i&1) | '0';
	buf[t] = 0;
	puts(buf);
	return;
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}