#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <functional>
#include <cmath>
#define SIZE 25
#define MX (1<<21)+2

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <int,string> PS;

vector < vector <int> > cnt[SIZE];
P nxt[SIZE][MX][2];
char str[MX];
int N,K;

//文字列は先頭から見ていく
void make()
{
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<(1<<i);j++)
		{
			for(int t=0;t<2;t++)
			{
				nxt[i][j][t]=P(-1,-1);
				if(i>0)
				{
					int S=j;
					for(int k=i-1;k>=0;k--)
					{
						if(t==1&&(S>>k&1))
						{
							nxt[i][j][t]=P(k,S-(1<<k));
							break;
						}
						else if(t==0&&!(S>>k&1))
						{
							nxt[i][j][t]=P(k,S);
							break;
						}
						if(S>>k&1) S-=(1<<k);
					}
				}
			}
		}
	}
}
PS solve(string now="",int dep=0)
{
	//深さ dep のを使う
	int sum=0;
	for(int i=0;i<=N-dep;i++)
	{
		for(int j=0;j<cnt[i][dep].size();j++)
		{
			sum+=cnt[i][dep][j];
		}
	}
	//printf("%d : %s\n",sum,now.c_str());
	if(sum<K) return PS(0,"");
	PS ans=PS(-dep,now);
	if(dep<N)
	{
		for(int t=0;t<2;t++)
		{
			string ns=now;
			if(t==0) ns+="0";
			else ns+="1";
			for(int i=0;i<N-dep;i++)
			{
				for(int j=0;j<cnt[i][dep+1].size();j++)
				{
					cnt[i][dep+1][j]=0;
				}
			}
			for(int i=0;i<=N-dep;i++)
			{
				for(int j=0;j<cnt[i][dep].size();j++)
				{
					P p=nxt[i][j][t];
					if(p!=P(-1,-1))
					{
						cnt[p.first][dep+1][p.second]+=cnt[i][dep][j];
					}
				}
			}
			ans=min(ans,solve(ns,dep+1));
		}
	}
	return ans;
}
int main()
{
	scanf("%d %d",&N,&K);
	make();
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=N-i;j++)
		{
			vector <int> v((1<<i));
			cnt[i].push_back(v);
		}
	}
	for(int i=0;i<=N;i++)
	{
		scanf("%s",&str);
		for(int j=0;j<1<<i;j++)
		{
			cnt[i][0][j]=str[j]-'0';
		}
	}
	PS ans=solve();
	printf("%s\n",ans.second.c_str());
	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>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <functional>
#include <cmath>
#define SIZE 25
#define MX (1<<21)+2

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <int,string> PS;

vector < vector <int> > cnt[SIZE];
P nxt[SIZE][MX][2];
char str[MX];
int N,K;

//文字列は先頭から見ていく
void make()
{
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<(1<<i);j++)
		{
			for(int t=0;t<2;t++)
			{
				nxt[i][j][t]=P(-1,-1);
				if(i>0)
				{
					int S=j;
					for(int k=i-1;k>=0;k--)
					{
						if(t==1&&(S>>k&1))
						{
							nxt[i][j][t]=P(k,S-(1<<k));
							break;
						}
						else if(t==0&&!(S>>k&1))
						{
							nxt[i][j][t]=P(k,S);
							break;
						}
						if(S>>k&1) S-=(1<<k);
					}
				}
			}
		}
	}
}
PS solve(string now="",int dep=0)
{
	//深さ dep のを使う
	int sum=0;
	for(int i=0;i<=N-dep;i++)
	{
		for(int j=0;j<cnt[i][dep].size();j++)
		{
			sum+=cnt[i][dep][j];
		}
	}
	//printf("%d : %s\n",sum,now.c_str());
	if(sum<K) return PS(0,"");
	PS ans=PS(-dep,now);
	if(dep<N)
	{
		for(int t=0;t<2;t++)
		{
			string ns=now;
			if(t==0) ns+="0";
			else ns+="1";
			for(int i=0;i<N-dep;i++)
			{
				for(int j=0;j<cnt[i][dep+1].size();j++)
				{
					cnt[i][dep+1][j]=0;
				}
			}
			for(int i=0;i<=N-dep;i++)
			{
				for(int j=0;j<cnt[i][dep].size();j++)
				{
					P p=nxt[i][j][t];
					if(p!=P(-1,-1))
					{
						cnt[p.first][dep+1][p.second]+=cnt[i][dep][j];
					}
				}
			}
			ans=min(ans,solve(ns,dep+1));
		}
	}
	return ans;
}
int main()
{
	scanf("%d %d",&N,&K);
	make();
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=N-i;j++)
		{
			vector <int> v((1<<i));
			cnt[i].push_back(v);
		}
	}
	for(int i=0;i<=N;i++)
	{
		scanf("%s",&str);
		for(int j=0;j<1<<i;j++)
		{
			cnt[i][0][j]=str[j]-'0';
		}
	}
	PS ans=solve();
	printf("%s\n",ans.second.c_str());
	return 0;
}

```