Score : $2300$ points

Problem Statement

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$.

3 4
1
01
1011
01001110

10

The following strings belong to $S$: the empty string, 1, 00, 10, 11, 001, 100, 101 and 110. The lexicographically smallest string among the longest strings that are subsequences of four or more of them is 10.

4 6
1
01
1011
10111010
1101110011111101

100

2 5
0
11
1111

The answer is the empty string.