#include <bits/stdc++.h>

using namespace std;

const int N=21,M=2100000;

typedef long long LL;

int n,K,s[N][M],f[N][M],fi[N][M][2],Out[N],two[N],h[N];

char S[N][M];

void Write(int x,int l)
{
	for (int i=l;i;i--,x>>=1) Out[i]=x&1;
	for (int i=1;i<=l;i++) printf("%d",Out[i]);
	exit(0);
}

int main()
{
	scanf("%d%d",&n,&K);
	for (int i=0;i<=n;i++) two[i]=1<<i;
	for (int i=1;i<=n;i++) h[i]=two[i]-1; h[0]=0;
	for (int i=0;i<=n;i++)
	{
		scanf("%s",S[i]);
		for (int j=0;j<two[i];j++) f[i][j]=S[i][j]-'0';
	}
	memset(fi,255,sizeof(fi));
	for (int l=1;l<=n;l++) for (int i=0;i<two[l];i++)
	{
		for (int j=0;j<l;j++) if (two[j]&i) fi[l][i][1]=j;else fi[l][i][0]=j;
	}
	for (int j=n;j;j--) for (int i=0;i<two[j];i++)
	{
		for (int l=0;l<=n-j;l++) for (int k=0;k<two[l];k++)
		{
			int st=i^(k+h[l]<<j),t1,t2;
			if (!f[j][st]) continue;
			if (fi[j][i][0]>=0)
			{
				t1=fi[j][i][0];
				t2=(i&two[fi[j][i][0]]-1)^((k<<1)+h[l+1]<<fi[j][i][0]);
				f[t1][t2]+=f[j][st];
			}
			if (fi[j][i][1]>=0)
			{
				t1=fi[j][i][1];
				t2=(i&two[fi[j][i][1]]-1)^((k<<1|1)+h[l+1]<<fi[j][i][1]);
				f[t1][t2]+=f[j][st];
			}
		}
	}
	for (int j=n;j>=0;j--)
	{
		for (int i=0;i<two[j];i++)
		{
			for (int l=0;l<=n-j;l++) for (int k=0;k<two[l];k++)
			{
				int st=i^(k+h[l]<<j);
				s[l][k]+=f[j][st];
			}
		}
	}
	for (int l=n;l;l--) for (int i=0;i<two[l];i++) if (s[l][i]>=K) Write(i,l);
	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;

const int N=21,M=2100000;

typedef long long LL;

int n,K,s[N][M],f[N][M],fi[N][M][2],Out[N],two[N],h[N];

char S[N][M];

void Write(int x,int l)
{
	for (int i=l;i;i--,x>>=1) Out[i]=x&1;
	for (int i=1;i<=l;i++) printf("%d",Out[i]);
	exit(0);
}

int main()
{
	scanf("%d%d",&n,&K);
	for (int i=0;i<=n;i++) two[i]=1<<i;
	for (int i=1;i<=n;i++) h[i]=two[i]-1; h[0]=0;
	for (int i=0;i<=n;i++)
	{
		scanf("%s",S[i]);
		for (int j=0;j<two[i];j++) f[i][j]=S[i][j]-'0';
	}
	memset(fi,255,sizeof(fi));
	for (int l=1;l<=n;l++) for (int i=0;i<two[l];i++)
	{
		for (int j=0;j<l;j++) if (two[j]&i) fi[l][i][1]=j;else fi[l][i][0]=j;
	}
	for (int j=n;j;j--) for (int i=0;i<two[j];i++)
	{
		for (int l=0;l<=n-j;l++) for (int k=0;k<two[l];k++)
		{
			int st=i^(k+h[l]<<j),t1,t2;
			if (!f[j][st]) continue;
			if (fi[j][i][0]>=0)
			{
				t1=fi[j][i][0];
				t2=(i&two[fi[j][i][0]]-1)^((k<<1)+h[l+1]<<fi[j][i][0]);
				f[t1][t2]+=f[j][st];
			}
			if (fi[j][i][1]>=0)
			{
				t1=fi[j][i][1];
				t2=(i&two[fi[j][i][1]]-1)^((k<<1|1)+h[l+1]<<fi[j][i][1]);
				f[t1][t2]+=f[j][st];
			}
		}
	}
	for (int j=n;j>=0;j--)
	{
		for (int i=0;i<two[j];i++)
		{
			for (int l=0;l<=n-j;l++) for (int k=0;k<two[l];k++)
			{
				int st=i^(k+h[l]<<j);
				s[l][k]+=f[j][st];
			}
		}
	}
	for (int l=n;l;l--) for (int i=0;i<two[l];i++) if (s[l][i]>=K) Write(i,l);
	return 0;
}
```