#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1<<21;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

int f[N][22];

int ans;
string str[21];
int n,m;
int main(){
   ans = 0;
   scanf("%d%d",&n,&m);
   memset(f,0,sizeof f);
   int cnt = 0;
   fr(i,0,n){
      cin >> str[i];
      fr(j,0,(1<<i)-1)if(str[i][j] == '1'){
         f[j+(1<<i)][i] = 1;
      }
   }

   nfr(msk,(1<<(n+1))-1,1){
      int leng = (int)log2(msk)-1;
      nfr(z,leng+1,1){
         int w = msk >> z;
         int w2 = msk % (1<<z);
         int curp = w2/(1<<(z-1));
         f[msk][z-1] += f[msk][z];
         int cz = z;
         while(cz > 0 && w2/(1<<(cz-1)) == curp){
            w2 %= (1<<(cz-1)); --cz;
         }
         if(cz){
            f[(w<<(cz))|((curp^1)<<(cz-1))|(w2%(1<<(cz-1)))][cz-1] += f[msk][z];
         }
         f[w][0] += f[msk][z];
      }
   }

   nfr(msk,(1<<(n+1))-1,1){
      if(f[msk][0] >= m){
         if((int)log2(msk) > (int)log2(ans))ans = msk;
         else if((int)log2(msk) == (int)log2(ans) && msk < ans)ans = msk;
      }
   }
   int w = (int)log2(ans);
   if(ans == 0)w = -1;
   nfr(i,w-1,0)printf("%c",(ans & (1<<i)) ? '1' : '0');
   puts(""); return 0;
}

### Prompt

Your task is to create 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;
typedef pair<int,int> pii;
const int N = 1<<21;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

int f[N][22];

int ans;
string str[21];
int n,m;
int main(){
   ans = 0;
   scanf("%d%d",&n,&m);
   memset(f,0,sizeof f);
   int cnt = 0;
   fr(i,0,n){
      cin >> str[i];
      fr(j,0,(1<<i)-1)if(str[i][j] == '1'){
         f[j+(1<<i)][i] = 1;
      }
   }

   nfr(msk,(1<<(n+1))-1,1){
      int leng = (int)log2(msk)-1;
      nfr(z,leng+1,1){
         int w = msk >> z;
         int w2 = msk % (1<<z);
         int curp = w2/(1<<(z-1));
         f[msk][z-1] += f[msk][z];
         int cz = z;
         while(cz > 0 && w2/(1<<(cz-1)) == curp){
            w2 %= (1<<(cz-1)); --cz;
         }
         if(cz){
            f[(w<<(cz))|((curp^1)<<(cz-1))|(w2%(1<<(cz-1)))][cz-1] += f[msk][z];
         }
         f[w][0] += f[msk][z];
      }
   }

   nfr(msk,(1<<(n+1))-1,1){
      if(f[msk][0] >= m){
         if((int)log2(msk) > (int)log2(ans))ans = msk;
         else if((int)log2(msk) == (int)log2(ans) && msk < ans)ans = msk;
      }
   }
   int w = (int)log2(ans);
   if(ans == 0)w = -1;
   nfr(i,w-1,0)printf("%c",(ans & (1<<i)) ? '1' : '0');
   puts(""); return 0;
}

```