#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int dp[21][1 << 21];
int zet[1 << 21];
int main()
{
	int num, gen;
	scanf("%d%d", &num, &gen);
	for (int i = 0; i < 21; i++)for (int j = 0; j < (1 << 21); j++)dp[i][j] = 0;
	fill(zet, zet + (1 << 21), 0);
	for (int i = 0; i <= num; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)dp[0][(1 << i) + j] = s[j] - '0';
	}
	for (int i = 0; i <= num; i++)
	{
		for (int j = i; j <= num; j++)
		{
			for (int k = 0; k < (1 << j); k++)
			{
				int x = dp[i][(1 << j) + k];
				int r1 = -1, r2 = -1;
				for (int l = i; l < j; l++)
				{
					if ((k&(1 << l)) == 0)
					{
						r1 = l;
						break;
					}
				}
				for (int l = i; l < j; l++)
				{
					if ((k&(1 << l)) != 0)
					{
						r2 = l;
						break;
					}
				}
				int s1 = ((k >> r1) << i) + (k&((1 << i) - 1)), s2 = ((k >> r2) << i) + (k&((1 << i) - 1));
				if (r1 != -1)dp[i + 1][(1 << (j - r1 + i)) + s1] += x;
				if (r2 != -1)dp[i + 1][(1 << (j - r2 + i)) + s2] += x;
				zet[(1 << i) + (k&((1 << i) - 1))] += x;
			}
		}
	}
	string ans;
	for (int i = num; i >= 0; i--)
	{
		for (int j = 0; j < (1 << i); j++)
		{
			//printf("%d %d %d\n", i, j, zet[(1 << i) + j]);
			if (zet[(1 << i) + j] >= gen)
			{
				for (int k = 0; k < i; k++)ans.push_back('0' + (((1 << k)&j) != 0));
				reverse(ans.begin(), ans.end());
				goto l01;
			}
		}
	}
l01:;
	cout << ans << endl;
}

### 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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int dp[21][1 << 21];
int zet[1 << 21];
int main()
{
	int num, gen;
	scanf("%d%d", &num, &gen);
	for (int i = 0; i < 21; i++)for (int j = 0; j < (1 << 21); j++)dp[i][j] = 0;
	fill(zet, zet + (1 << 21), 0);
	for (int i = 0; i <= num; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)dp[0][(1 << i) + j] = s[j] - '0';
	}
	for (int i = 0; i <= num; i++)
	{
		for (int j = i; j <= num; j++)
		{
			for (int k = 0; k < (1 << j); k++)
			{
				int x = dp[i][(1 << j) + k];
				int r1 = -1, r2 = -1;
				for (int l = i; l < j; l++)
				{
					if ((k&(1 << l)) == 0)
					{
						r1 = l;
						break;
					}
				}
				for (int l = i; l < j; l++)
				{
					if ((k&(1 << l)) != 0)
					{
						r2 = l;
						break;
					}
				}
				int s1 = ((k >> r1) << i) + (k&((1 << i) - 1)), s2 = ((k >> r2) << i) + (k&((1 << i) - 1));
				if (r1 != -1)dp[i + 1][(1 << (j - r1 + i)) + s1] += x;
				if (r2 != -1)dp[i + 1][(1 << (j - r2 + i)) + s2] += x;
				zet[(1 << i) + (k&((1 << i) - 1))] += x;
			}
		}
	}
	string ans;
	for (int i = num; i >= 0; i--)
	{
		for (int j = 0; j < (1 << i); j++)
		{
			//printf("%d %d %d\n", i, j, zet[(1 << i) + j]);
			if (zet[(1 << i) + j] >= gen)
			{
				for (int k = 0; k < i; k++)ans.push_back('0' + (((1 << k)&j) != 0));
				reverse(ans.begin(), ans.end());
				goto l01;
			}
		}
	}
l01:;
	cout << ans << endl;
}

```