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:
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

const int base = 1000000000;
const int base_digits = 9;
#define bg bigint_t
struct bigint_t {
  vector<int> z;
  int sign;

  bigint_t() : sign(1) {}

  bigint_t(long long v) { *this = v; }

  bigint_t(const string &s) { read(s); }

  void operator=(const bigint_t &v) {
    sign = v.sign;
    z = v.z;
  }

  void operator=(long long v) {
    sign = 1;
    if (v < 0) {
      sign = -1, v = -v;
    }
    z.clear();
    for (; v > 0; v = v / base) {
      z.push_back(v % base);
    }
  }

  bigint_t operator+(const bigint_t &v) const {
    if (sign == v.sign) {
      bigint_t res = v;

      for (int i = 0, carry = 0; i < (int) max(z.size(), v.z.size()) || carry; ++i) {
        if (i == (int) res.z.size()) {
          res.z.push_back(0);
        }
        res.z[i] += carry + (i < (int) z.size() ? z[i] : 0);
        carry = res.z[i] >= base;
        if (carry) {
          res.z[i] -= base;
        }
      }
      return res;
    } else {
      return *this - (-v);
    }
  }

  bigint_t operator-(const bigint_t &v) const {
    if (sign == v.sign) {
      if (abs() >= v.abs()) {
        bigint_t res = *this;
        for (int i = 0, carry = 0; i < (int) v.z.size() || carry; ++i) {
          res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : 0);
          carry = res.z[i] < 0;
          if (carry) {
            res.z[i] += base;
          }
        }
        res.trim();
        return res;
      } else {
        return -(v - *this);
      }
    } else {
      return *this + (-v);
    }
  }

  void operator*=(int v) {
    if (v < 0) {
      sign = -sign, v = -v;
    }
    for (int i = 0, carry = 0; i < (int) z.size() || carry; ++i) {
      if (i == (int) z.size()) {
        z.push_back(0);
      }
      long long cur = (long long)z[i] * v + carry;
      carry = cur / base;
      z[i] = cur % base;
      // asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
    }
    trim();
  }

  bigint_t operator*(int v) const {
    bigint_t res = *this;
    res *= v;
    return res;
  }

  friend pair<bigint_t, bigint_t> divmod(const bigint_t &a1,
                                         const bigint_t &b1) {
    int norm = base / (b1.z.back() + 1);
    bigint_t a = a1.abs() * norm;
    bigint_t b = b1.abs() * norm;
    bigint_t q, r;
    q.z.resize(a.z.size());

    for (int i = a.z.size() - 1; i >= 0; i--) {
      r *= base;
      r += a.z[i];
      int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
      int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
      int d = ((long long)s1 * base + s2) / b.z.back();
      r -= b * d;
      while (r < 0) {
        r += b, --d;
      }
      q.z[i] = d;
    }

    q.sign = a1.sign * b1.sign;
    r.sign = a1.sign;
    q.trim();
    r.trim();
    return make_pair(q, r / norm);
  }

  friend bigint_t sqrt(const bigint_t &a1) {
    bigint_t a = a1;
    while (a.z.empty() || a.z.size() % 2 == 1) {
      a.z.push_back(0);
    }

    int n = a.z.size();

    int firstDigit = sqrt((long long)a.z[n - 1] * base + a.z[n - 2]);
    int norm = base / (firstDigit + 1);
    a *= norm;
    a *= norm;
    while (a.z.empty() || a.z.size() % 2 == 1) {
      a.z.push_back(0);
    }

    bigint_t r = (long long)a.z[n - 1] * base + a.z[n - 2];
    firstDigit = sqrt((long long)a.z[n - 1] * base + a.z[n - 2]);
    int q = firstDigit;
    bigint_t res;

    for (int j = n / 2 - 1; j >= 0; j--) {
      for (;; --q) {
        bigint_t r1 =
            (r - (res * 2 * base + q) * q) * base * base +
            (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
        if (r1 >= 0) {
          r = r1;
          break;
        }
      }
      res *= base;
      res += q;

      if (j > 0) {
        int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
        int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
        int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
        q = ((long long)d1 * base * base + (long long)d2 * base + d3) /
            (firstDigit * 2);
      }
    }

    res.trim();
    return res / norm;
  }

  bigint_t operator/(const bigint_t &v) const { return divmod(*this, v).first; }

  bigint_t operator%(const bigint_t &v) const {
    return divmod(*this, v).second;
  }

  void operator/=(int v) {
    if (v < 0) {
      sign = -sign, v = -v;
    }
    for (int i = z.size() - 1, rem = 0; i >= 0; --i) {
      long long cur = z[i] + (long long)rem * base;
      z[i] = cur / v;
      rem = cur % v;
    }
    trim();
  }

  bigint_t operator/(int v) const {
    bigint_t res = *this;
    res /= v;
    return res;
  }

  int operator%(int v) const {
    if (v < 0) {
      v = -v;
    }
    int m = 0;
    for (int i = z.size() - 1; i >= 0; --i) {
      m = ((long long)m * base + z[i]) % v;
    }
    return m * sign;
  }

  void operator+=(const bigint_t &v) { *this = *this + v; }
  void operator-=(const bigint_t &v) { *this = *this - v; }
  void operator*=(const bigint_t &v) { *this = *this * v; }
  void operator/=(const bigint_t &v) { *this = *this / v; }

  bool operator<(const bigint_t &v) const {
    if (sign != v.sign) {
      return sign < v.sign;
    }
    if (z.size() != v.z.size()) {
      return z.size() * sign < v.z.size() * v.sign;
    }
    for (int i = z.size() - 1; i >= 0; i--) {
      if (z[i] != v.z[i]) {
        return z[i] * sign < v.z[i] * sign;
      }
    }
    return false;
  }

  bool operator>(const bigint_t &v) const { return v < *this; }
  bool operator<=(const bigint_t &v) const { return !(v < *this); }
  bool operator>=(const bigint_t &v) const { return !(*this < v); }
  bool operator==(const bigint_t &v) const {
    return !(*this < v) && !(v < *this);
  }
  bool operator!=(const bigint_t &v) const { return *this < v || v < *this; }

  void trim() {
    while (!z.empty() && z.back() == 0) {
      z.pop_back();
    }
    if (z.empty()) {
      sign = 1;
    }
  }

  bool isZero() const { return z.empty() || (z.size() == 1 && !z[0]); }

  bigint_t operator-() const {
    bigint_t res = *this;
    res.sign = -sign;
    return res;
  }

  bigint_t abs() const {
    bigint_t res = *this;
    res.sign *= res.sign;
    return res;
  }

  long long longValue() const {
    long long res = 0;
    for (int i = z.size() - 1; i >= 0; i--) {
      res = res * base + z[i];
    }
    return res * sign;
  }

  friend bigint_t gcd(const bigint_t &a, const bigint_t &b) {
    return b.isZero() ? a : gcd(b, a % b);
  }
  friend bigint_t lcm(const bigint_t &a, const bigint_t &b) {
    return a / gcd(a, b) * b;
  }

  void read(const string &s) {
    sign = 1;
    z.clear();
    int pos = 0;
    while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
      if (s[pos] == '-') {
        sign = -sign;
      }
      ++pos;
    }
    for (int i = s.size() - 1; i >= pos; i -= base_digits) {
      int x = 0;
      for (int j = max(pos, i - base_digits + 1); j <= i; j++) {
        x = x * 10 + s[j] - '0';
      }
      z.push_back(x);
    }
    trim();
  }

  friend istream &operator>>(istream &stream, bigint_t &v) {
    string s;
    stream >> s;
    v.read(s);
    return stream;
  }

  friend ostream &operator<<(ostream &stream, const bigint_t &v) {
    if (v.sign == -1) {
      stream << '-';
    }
    stream << (v.z.empty() ? 0 : v.z.back());
    for (int i = v.z.size() - 2; i >= 0; --i) {
      stream << setw(base_digits) << setfill('0') << v.z[i];
    }
    return stream;
  }

  static vector<int> convert_base(const vector<int> &a, int old_digits,
                                  int new_digits) {
    vector<long long> p(max(old_digits, new_digits) + 1);
    p[0] = 1;
    for (int i = 1; i < (int) p.size(); i++) {
      p[i] = p[i - 1] * 10;
    }
    vector<int> res;
    long long cur = 0;
    int cur_digits = 0;
    for (int i = 0; i < (int) a.size(); i++) {
      cur += a[i] * p[cur_digits];
      cur_digits += old_digits;
      while (cur_digits >= new_digits) {
        res.push_back(cur % p[new_digits]);
        cur /= p[new_digits];
        cur_digits -= new_digits;
      }
    }
    res.push_back(cur);
    while (!res.empty() && res.back() == 0) {
      res.pop_back();
    }
    return res;
  }

  typedef vector<long long> vll;

  static vll karatsubaMultiply(const vll &a, const vll &b) {
    int n = a.size();
    vll res(n + n);
    if (n <= 32) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          res[i + j] += a[i] * b[j];
        }
      }
      return res;
    }

    int k = n >> 1;
    vll a1(a.begin(), a.begin() + k);
    vll a2(a.begin() + k, a.end());
    vll b1(b.begin(), b.begin() + k);
    vll b2(b.begin() + k, b.end());

    vll a1b1 = karatsubaMultiply(a1, b1);
    vll a2b2 = karatsubaMultiply(a2, b2);

    for (int i = 0; i < k; i++) {
      a2[i] += a1[i];
    }
    for (int i = 0; i < k; i++) {
      b2[i] += b1[i];
    }

    vll r = karatsubaMultiply(a2, b2);
    for (int i = 0; i < (int) a1b1.size(); i++) {
      r[i] -= a1b1[i];
    }
    for (int i = 0; i < (int) a2b2.size(); i++) {
      r[i] -= a2b2[i];
    }

    for (int i = 0; i < (int) r.size(); i++) {
      res[i + k] += r[i];
    }
    for (int i = 0; i < (int) a1b1.size(); i++) {
      res[i] += a1b1[i];
    }
    for (int i = 0; i < (int) a2b2.size(); i++) {
      res[i + n] += a2b2[i];
    }
    return res;
  }

  bigint_t operator*(const bigint_t &v) const {
    vector<int> a6 = convert_base(this->z, base_digits, 6);
    vector<int> b6 = convert_base(v.z, base_digits, 6);
    vll a(a6.begin(), a6.end());
    vll b(b6.begin(), b6.end());
    while (a.size() < b.size()) {
      a.push_back(0);
    }
    while (b.size() < a.size()) {
      b.push_back(0);
    }
    while (a.size() & (a.size() - 1)) {
      a.push_back(0);
      b.push_back(0);
    }
    vll c = karatsubaMultiply(a, b);
    bigint_t res;
    res.sign = sign * v.sign;
    for (int i = 0, carry = 0; i < (int) c.size(); i++) {
      long long cur = c[i] + carry;
      res.z.push_back(cur % 1000000);
      carry = cur / 1000000;
    }
    res.z = convert_base(res.z, 6, base_digits);
    res.trim();
    return res;
  }
};

int n, b;

int main() {
  cin >> n >> b;
  bigint_t B = 1;
  for(int i = 0; i < b; i++) B *= 2;
  vector<bigint_t> power(n + 1);
  power[0] = 1;
  for(int i = 1; i <= n; i++) power[i] = power[i - 1] * 2;
  auto to_string = [&](bigint_t c) {
    string r;
    for(int i = 0; i < b; i++) {
      if((c % 2) == 1) r += '1';
      else r += '0';
      c /= 2;
    }
    reverse(r.begin(), r.end());
    return r;
  };
  int bound = 3 * (n + b);
  auto ask = [&](int id, bigint_t c) {
    assert(bound);
    bound--;
    cout << id + 1 << " " << to_string(c) << endl;
    string v;
    cin >> v;
    return v == "yes";
  };
  bigint_t L = 0;
  vector<bigint_t> R(n, B - 1);
  vector<int> dead(n);
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  auto calc = [&](bigint_t p) {
    bigint_t sum = 0;
    for(int i = 0; i < (int) order.size(); i++) {
      int id = order[i];
      bigint_t nxt = (i < (int) order.size() - 1 ? R[order[i + 1]] : p);
      sum += power[i + 1] * (R[id] - nxt);
    }
    bigint_t pos;
    bigint_t cur = 0;
    for(int i = 0; i < (int) order.size(); i++) {
      int id = order[i];
      bigint_t nxt = (i < (int) order.size() - 1 ? R[order[i + 1]] : p);
      cur += power[i + 1] * (R[id] - nxt);
      if(cur * 3 >= sum * 2) {
        bigint_t pr = cur - power[i + 1] * (R[id] - nxt);
        bigint_t to = (sum * 2 + 2) / 3;
        bigint_t ad = (to - pr + power[i + 1] - 1) / power[i + 1];
        // pr + ad * power[i + 1] >= to
        pos = R[id] - ad;
        break;
      }
    }
    return pos;
  };
  while(true) {
    bigint_t pos = calc(L);
    int id = order[0];
    if(ask(id, pos)) {
      L = pos + 1;
      for(int i = 0; i < n; i++) if(R[i] <= L) dead[i] = 1;
    } else {
      R[id] = pos;
      if(R[id] <= L) dead[id] = 1;
    }
    if(count(dead.begin(), dead.end(), 1) == n) {
      break;
    }
    vector<int> new_order;
    for(int i : order) if(!dead[i]) new_order.push_back(i);
    swap(order, new_order);
    int cur = 0;
    while(cur < (int) order.size() - 1 && R[order[cur]] < R[order[cur + 1]]) {
      swap(order[cur], order[cur + 1]);
      cur++;
    }
  }
  cout << 0 << " " << to_string(L) << endl;
  return 0;
}