#include <cstdio>

using namespace std;

struct List {
    int* cnt[25];
};

int n, k;

char str[1100000];

int high_len;
int high_str;

void work(List& lst, int cur_len, int cur_str)
{
    List new_list;
    int lst_total = 0;
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            lst_total += lst.cnt[i][j];
        }
    }
    if (lst_total < k) return;
    //printf("%d %d\n", cur_len, cur_str);
    if (cur_len > high_len || (cur_len == high_len && cur_str < high_str)) {
        high_len = cur_len; high_str = cur_str;
    }
    if (cur_len == n) return;
    for (int i = 0; i <= n - cur_len - 1; i++) {
        new_list.cnt[i] = new int[1 << i];
        for (int j = 0; j < (1 << i); j++) {
            new_list.cnt[i][j] = 0;
        }
    }
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            if (!lst.cnt[i][j]) continue;
            for (int bt = i - 1; bt >= 0; bt--) {
                int bt_val = (j & (1 << bt)) ? 1 : 0;
                if (bt_val == 0) {
                    new_list.cnt[bt][j & ((1 << bt) - 1)] += lst.cnt[i][j]; break;
                }
            }
        }
    }
    work(new_list, cur_len + 1, cur_str * 2);
    for (int i = 0; i <= n - cur_len - 1; i++) {
        for (int j = 0; j < (1 << i); j++) {
            new_list.cnt[i][j] = 0;
        }
    }
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            if (!lst.cnt[i][j]) continue;
            for (int bt = i - 1; bt >= 0; bt--) {
                int bt_val = (j & (1 << bt)) ? 1 : 0;
                if (bt_val == 1) {
                    new_list.cnt[bt][j & ((1 << bt) - 1)] += lst.cnt[i][j]; break;
                }
            }
        }
    }
    work(new_list, cur_len + 1, cur_str * 2 + 1);
    for (int i = 0; i <= n - cur_len - 1; i++) {
        delete[] new_list.cnt[i];
    }
}

int main()
{
    List x;
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; i++) {
        x.cnt[i] = new int[1 << i];
        scanf("%s", str);
        for (int j = 0; j < (1 << i); j++) {
            x.cnt[i][j] = (str[j] == '1' ? 1 : 0);
        }
    }
    work(x, 0, 0);
    for (int i = high_len - 1; i >= 0; i--) {
        printf("%c", (high_str & (1 << i)) ? '1' : '0');
    }
    return 0;
}

### Prompt

In CPP, your task is to solve 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 <cstdio>

using namespace std;

struct List {
    int* cnt[25];
};

int n, k;

char str[1100000];

int high_len;
int high_str;

void work(List& lst, int cur_len, int cur_str)
{
    List new_list;
    int lst_total = 0;
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            lst_total += lst.cnt[i][j];
        }
    }
    if (lst_total < k) return;
    //printf("%d %d\n", cur_len, cur_str);
    if (cur_len > high_len || (cur_len == high_len && cur_str < high_str)) {
        high_len = cur_len; high_str = cur_str;
    }
    if (cur_len == n) return;
    for (int i = 0; i <= n - cur_len - 1; i++) {
        new_list.cnt[i] = new int[1 << i];
        for (int j = 0; j < (1 << i); j++) {
            new_list.cnt[i][j] = 0;
        }
    }
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            if (!lst.cnt[i][j]) continue;
            for (int bt = i - 1; bt >= 0; bt--) {
                int bt_val = (j & (1 << bt)) ? 1 : 0;
                if (bt_val == 0) {
                    new_list.cnt[bt][j & ((1 << bt) - 1)] += lst.cnt[i][j]; break;
                }
            }
        }
    }
    work(new_list, cur_len + 1, cur_str * 2);
    for (int i = 0; i <= n - cur_len - 1; i++) {
        for (int j = 0; j < (1 << i); j++) {
            new_list.cnt[i][j] = 0;
        }
    }
    for (int i = 0; i <= n - cur_len; i++) {
        for (int j = 0; j < (1 << i); j++) {
            if (!lst.cnt[i][j]) continue;
            for (int bt = i - 1; bt >= 0; bt--) {
                int bt_val = (j & (1 << bt)) ? 1 : 0;
                if (bt_val == 1) {
                    new_list.cnt[bt][j & ((1 << bt) - 1)] += lst.cnt[i][j]; break;
                }
            }
        }
    }
    work(new_list, cur_len + 1, cur_str * 2 + 1);
    for (int i = 0; i <= n - cur_len - 1; i++) {
        delete[] new_list.cnt[i];
    }
}

int main()
{
    List x;
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; i++) {
        x.cnt[i] = new int[1 << i];
        scanf("%s", str);
        for (int j = 0; j < (1 << i); j++) {
            x.cnt[i][j] = (str[j] == '1' ? 1 : 0);
        }
    }
    work(x, 0, 0);
    for (int i = high_len - 1; i >= 0; i--) {
        printf("%c", (high_str & (1 << i)) ? '1' : '0');
    }
    return 0;
}

```