Problem: What walks on four feet in the morning, two in the afternoon, and three at night?

This is an interactive problem. This problem doesn't support hacks.

Sphinx's duty is to guard the city of Thebes by making sure that no unworthy traveler crosses its gates. Only the ones who answer her riddle timely and correctly (or get an acc for short) are allowed to pass. As of those who fail, no one heard of them ever again...

So you don't have a choice but to solve the riddle. Sphinx has an array a_1, a_2, …, a_n of nonnegative integers strictly smaller than 2^b and asked you to find the maximum value among its elements. Of course, she will not show you the array, but she will give you n and b. As it is impossible to answer this riddle blindly, you can ask her some questions. For given i, y, she'll answer you whether a_i is bigger than y. As sphinxes are not very patient, you can ask at most 3 ⋅ (n + b)  such questions.

Although cunning, sphinxes are honest. Even though the array can change between your queries, answers to the previously asked questions will remain valid.

Input

The first line contains two integers n and b (1 ≤ n, b ≤ 200). The remaining parts of the input will be given throughout the interaction process.

Interaction

In each round your program must output a single line with an integer i (0 ≤ i ≤ n) and a binary string of length exactly b denoting the binary representation of y (most significant bit first).

If i > 0, this line encodes the question: Is a_i bigger than y?. There should be at most 3 ⋅ (n+b) such lines; after each of them, the interactor will print yes or no in a single line.

If i = 0, this is the last round of interaction, after which your program should terminate, and y should be the maximal value among the elements of Sphinx's array. Note that this round does not count to the query limit.

Note that the interactor is adaptive.

After printing a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * see the documentation for other languages.



If your solution does not correctly follow the interaction guideline above, it may receive an arbitrary verdict. Otherwise, your program will receive the Wrong Answer judgment if it reports the wrong maximum.

Examples

Input


5 3

yes

no

no

no

no

yes


Output


5 101

5 110

4 100

3 101

2 001

1 000

0 110


Input


4 3

no

no

no

no


Output


1 000

2 000

3 000

4 000

0 000


Input


1 1


Output


0 0

Note

In all examples, the sequence is fixed beforehand.

In the first example, the sequence is 2, 1, 4, 0, 6.

In the second example, the sequence is 0, 0, 0, 0.

In the third example, the sequence is 0.

Note that if the interactor was adaptive, then the interaction in the first and the third example would not be sufficient to return the correct value of maximum.

Solution (in CPP):

Solution:
//#define DEBUG
//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#if __cplusplus < 201500L
#include <bits/stdc++.h>
#else
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <cmath>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <tuple>
#endif

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef map<string, int> mpsi;
typedef map<double, int> mpdi;
typedef map<int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 1 }, {
		1, 1 }, { 1, -1 }, { -1, -1 } };

template<class T> inline T abs1(T a) {
	return a < 0 ? -a : a;
}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template<typename t, typename t1>
t min1(t a, t1 b) {
	return a < b ? a : b;
}
template<typename t, typename ... arg>
t min1(t a, arg ... arr) {
	return min1(a, min1(arr...));
}
template<typename t, typename t1>
t max1(t a, t1 b) {
	return a > b ? a : b;
}
template<typename t, typename ... arg>
t max1(t a, arg ... arr) {
	return max1(a, max1(arr...));
}
#endif

inline int jud(double a, double b) {
	if (abs(a) < eps && abs(b) < eps)
		return 0;
	else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
	if (a < b) return -1;
	return 1;
}
template<typename t> inline int jud(t a, t b) {
	if (a < b) return -1;
	if (a == b) return 0;
	return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template<typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
	if (na == 0) return 0;
	int be = 0, en = na - 1;
	if (*a <= *(a + na - 1)) {
		if (f_lb == 0)
			while (be < en) {
				int mid = (be + en + 1) / 2;
				if (jud(*(a + mid), val) != 1)
					be = mid;
				else
					en = mid - 1;
			}
		else
			while (be < en) {
				int mid = (be + en) / 2;
				if (jud(*(a + mid), val) != -1)
					en = mid;
				else
					be = mid + 1;
			}
		if (f_small && jud(*(a + be), val) == 1) be--;
		if (!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if (f_lb)
			while (be < en) {
				int mid = (be + en + 1) / 2;
				if (jud(*(a + mid), val) != -1)
					be = mid;
				else
					en = mid - 1;
			}
		else
			while (be < en) {
				int mid = (be + en) / 2;
				if (jud(*(a + mid), val) != 1)
					en = mid;
				else
					be = mid + 1;
			}
		if (!f_small && jud(*(a + be), val) == -1) be--;
		if (f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}

template<class T> inline T lowb(T num) {
	return num & (-num);
}
#ifdef GPP
inline int bitnum(ui nValue) {
	return __builtin_popcount(nValue);
}
inline int bitnum(int nValue) {
	return __builtin_popcount(nValue);
}
inline int bitnum(ull nValue) {
	return __builtin_popcountll(nValue);
}
inline int bitnum(ll nValue) {
	return __builtin_popcountll(nValue);
}
inline int bitmaxl(ui a) {
	if (a == 0) return 0;
	return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
	if (a == 0) return 0;
	return 32 - __builtin_clz(a);
}
inline int bitmaxl(ull a) {
	if (a == 0) return 0;
	return 64 - __builtin_clzll(a);
}
inline int bitmaxl(ll a) {
	if (a == 0) return 0;
	return 64 - __builtin_clzll(a);
}
#else
#endif

long long pow(long long n, long long m, long long mod = 0) {
	if (m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while (m) {
		if (m & 1) {
			ans *= k;
			if (mod) ans %= mod;
		}
		k *= k;
		if (mod) k %= mod;
		m >>= 1;
	}
	return ans;
}

#define  MOD 1000000007
template<class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
	if (mod == -1) mod = MOD;
	a += b;
	while (a >= mod)
		a -= mod;
	while (a < 0)
		a += mod;
}
template<class t>
void output1(t arr) {
	for (int i = 0; i < (int) arr.size(); i++)
		cerr << arr[i] << ' ';
	cerr << endl;
}
template<class t>
void output2(t arr) {
	for (int i = 0; i < (int) arr.size(); i++)
		output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> bin_gen(0, 1);
std::uniform_int_distribution<int> n_gen(1, 50);
std::uniform_int_distribution<int> b_gen(1, 50);

int rn, rb;
vs orig;

void GenerateData() {
//	rn = 3;
//	rb = 200;
//	cout << rn << ' ' << rb << endl;
//	for (int i = 0; i < rn; i++) {
//		string str = "";
//		for (int j = 0; j < rb; j++) {
//			str += bin_gen(rng) + '0';
//		}
//		orig.push_back(str);
//		cout << str << endl;
//	}
	rn = 100;
	rb = 200;
	for (int i = 0; i < rn; i++) {
		string str = string(200, '0');
		str[199] = '1';
		if (rn - i <= 2) {
			str[0] = '1';
		}
		orig.push_back(str);
	}
//	rn = 32;
//	rb = 200;
//	cerr << rn << ' ' << rb << endl;
//	for (int i = 0; i < rn; i++) {
//		int delta = (1 << rb) / rn;
//		int num = i * delta + std::uniform_int_distribution<int>(0, delta - 1)(rng);
//		string str = "";
//		for (int j = 0; j < rb; j++) {
//			if (j > rb - 40 && ((1ll << (rb - j - 1)) & num)) {
//				str += '1';
//			} else {
//				str += '0';
//			}
//		}
//		orig.push_back(str);
//		cerr  << str << endl;
//	}
}

int ask_cnt = 0;
int Ask(int idx, const string& str) {
	ask_cnt++;
	printf("%d %s\n", idx + 1, str.c_str());
#ifdef DEBUG
	if (orig[idx] > str) {
		return 1;
	}
	return 0;
#else
	fflush(stdout);
	char ans[5];
	scanf("%s", ans);
	if (string(ans) == "yes") return 1;
	else return 0;
#endif
}

int Answer(const string& str) {
	printf("0 %s\n", str.c_str());
	return 0;
}

int n, b;

string cur;
int cur_idx;
pii st[1210];
int lst;

int main() {

//............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！...................................................

#ifdef DEBUG //......................................................................................................
	GenerateData();
	freopen("input.txt", "w", stdout);
#endif //...........................................................................................................

#ifdef DEBUG
	n = rn, b = rb;
#else
	scanf("%d%d", &n, &b);
#endif

	for (int i = 0; i < n; i++) {
		st[lst++] = mpr(i, 0);
	}
	cur_idx = 0;
	cur = string(b, '0');
	vector<tuple<int, int, int>> history;
	for (int i = 0; i < lst; i++) {
		string rstr;
		rstr = cur;
		if (cur_idx < b) rstr[cur_idx] = '0';
		for (int j = cur_idx + 1; j < b; j++) rstr[j] = '1';
		if ( Ask(st[i].first, rstr)) {
			bool flag = false;
			do {
				int rcur_idx = cur_idx - 1;
				if (rcur_idx < st[i].second) break;
				for (; rcur_idx >= 0; rcur_idx--) if (cur[rcur_idx] == '0') {
					break;
				}
				rstr = cur;
				for (int j = rcur_idx + 1; j < b; j++) rstr[j] = '1';
				flag = Ask(st[i].first, rstr);
				if (flag) {
					cur_idx = rcur_idx;
					while (st[lst - 1].second > cur_idx && lst > i) lst--;
				}
			} while(flag);
			if (cur_idx < b) {
				cur[cur_idx] = '1';
				st[lst++] = mpr(st[i].first, cur_idx + 1);
				cur_idx++;
			}
		} else if (cur_idx < b) {
			rstr[cur_idx] = '0';
			for (int j = cur_idx + 1; j < b; j++) rstr[j] = '0';
			if (Ask(st[i].first, rstr)) {
				cur[cur_idx] = '0';
				st[lst++] = mpr(st[i].first, cur_idx + 1);
				cur_idx++;
			}
		}
	}

	for (int i = cur_idx; i < b; i++) cur[i] = '0';
	Answer(cur);

	return 0;
}