#include<bits/stdc++.h>

using namespace std;

int N, K, mask[22][22], dp[22][(1 << 21) + 10], finalCount[(1 << 21) + 10], firstAppearance[2][(1 << 21) + 10], length[(1 << 21) + 10];
char sir[(1 << 21) + 2];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d\n", &N, &K);
for (int l=0; l<=N; l++)
{
    scanf ("%s", sir);
    for (int j=0; j<(1 << l); j++)
    {
        if (sir[j] == '1')
            dp[0][j | (1 << l)] ++;
        length[j | (1 << l)] = l;
    }
}
for (int i=0; i<(1 << (N + 1)); i++)
{
    firstAppearance[0][i] = firstAppearance[1][i] = -1;
    bool bit = i & 1;
    firstAppearance[bit][i] = i >> 1;
    if (firstAppearance[bit ^ 1][i >> 1] != -1)
        firstAppearance[bit ^ 1][i] = firstAppearance[bit ^ 1][i >> 1];
}
for (int i=0; i<=N + 1; i++)
    for (int j=i; j<=N + 1; j++)
        for (int k=i; k<=j; k++)
            mask[i][j] |= 1 << k;
for (int i=0; i<=N; i++)
    for (int j=1; j<(1 << (N + 1)); j++)
        if (dp[i][j] > 0)
        {
            int L = length[j], before = j & (i == 0 ? 0 : mask[0][i - 1]), after = (j & mask[i][L]) >> i;
            finalCount[before | (1 << i)] += dp[i][j];
            if (i < N)
            {
                for (int k=0; k<2; k++)
                    if (firstAppearance[k][after] > 0)
                    {
                        int newBefore = before, newAfter = firstAppearance[k][after];
                        if (k) newBefore |= 1 << i;
                        dp[i + 1][newBefore | (newAfter << (i + 1))] += dp[i][j];
                    }
            }
        }
int maxL = 0, how = 0;
for (int i=1; i<(1 << (N + 1)); i++)
    if (finalCount[i] >= K && length[i] > maxL)
        maxL = length[i], how = i;
    else
    if (finalCount[i] >= K && length[i] == maxL)
    {
        for (int k=maxL - 1; k>=0; k--)
            if (((i >> k) & 1) ^ ((how >> k) & 1))
            {
                if (how & (1 << k))
                    how = i;
                break;
            }
    }
for (int i=maxL - 1; i>=0; i--)
    if (how & (1 << i)) printf ("1");
    else printf ("0");
printf ("\n");
return 0;
}

### Prompt

Your challenge is to write 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;

int N, K, mask[22][22], dp[22][(1 << 21) + 10], finalCount[(1 << 21) + 10], firstAppearance[2][(1 << 21) + 10], length[(1 << 21) + 10];
char sir[(1 << 21) + 2];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d\n", &N, &K);
for (int l=0; l<=N; l++)
{
    scanf ("%s", sir);
    for (int j=0; j<(1 << l); j++)
    {
        if (sir[j] == '1')
            dp[0][j | (1 << l)] ++;
        length[j | (1 << l)] = l;
    }
}
for (int i=0; i<(1 << (N + 1)); i++)
{
    firstAppearance[0][i] = firstAppearance[1][i] = -1;
    bool bit = i & 1;
    firstAppearance[bit][i] = i >> 1;
    if (firstAppearance[bit ^ 1][i >> 1] != -1)
        firstAppearance[bit ^ 1][i] = firstAppearance[bit ^ 1][i >> 1];
}
for (int i=0; i<=N + 1; i++)
    for (int j=i; j<=N + 1; j++)
        for (int k=i; k<=j; k++)
            mask[i][j] |= 1 << k;
for (int i=0; i<=N; i++)
    for (int j=1; j<(1 << (N + 1)); j++)
        if (dp[i][j] > 0)
        {
            int L = length[j], before = j & (i == 0 ? 0 : mask[0][i - 1]), after = (j & mask[i][L]) >> i;
            finalCount[before | (1 << i)] += dp[i][j];
            if (i < N)
            {
                for (int k=0; k<2; k++)
                    if (firstAppearance[k][after] > 0)
                    {
                        int newBefore = before, newAfter = firstAppearance[k][after];
                        if (k) newBefore |= 1 << i;
                        dp[i + 1][newBefore | (newAfter << (i + 1))] += dp[i][j];
                    }
            }
        }
int maxL = 0, how = 0;
for (int i=1; i<(1 << (N + 1)); i++)
    if (finalCount[i] >= K && length[i] > maxL)
        maxL = length[i], how = i;
    else
    if (finalCount[i] >= K && length[i] == maxL)
    {
        for (int k=maxL - 1; k>=0; k--)
            if (((i >> k) & 1) ^ ((how >> k) & 1))
            {
                if (how & (1 << k))
                    how = i;
                break;
            }
    }
for (int i=maxL - 1; i>=0; i--)
    if (how & (1 << i)) printf ("1");
    else printf ("0");
printf ("\n");
return 0;
}

```