#include "ancient2.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


namespace {

constexpr int N = 1000;
constexpr int M = 102;

using BS = bitset<N + 1>;

BS a[N];

bool canAdd(BS bs) {
  for (int i = 0; i < N; ++i) if (bs[i] && a[i][i]) {
    bs ^= a[i];
  }
  const int i = bs._Find_first();
  return (i < N);
}
void add(BS bs) {
  for (int i = 0; i < N; ++i) if (bs[i] && a[i][i]) {
    bs ^= a[i];
  }
  const int i = bs._Find_first();
  assert(i < N);
  a[i] = bs;
}

}  // namespace

std::string Solve(int N_) {
  assert(N == N_);
  
  // prefix
  {
    string s(N, '?');
    for (int i = 0; i < M - 2; ++i) {
      s[i] = '1';
      const int V = i + 3;
      vector<int> to[2];
      for (int e = 0; e < 2; ++e) {
        to[e].assign(V, -1);
      }
      for (int j = 0; j <= i; ++j) {
        const int e = s[j] - '0';
        to[e][j] = j + 1;
        to[e ^ 1][j] = i + 2;
      }
      for (int e = 0; e < 2; ++e) {
        to[e][i + 1] = i + 1;
        to[e][i + 2] = i + 2;
      }
      const int res = Query(V, to[0], to[1]);
      assert(res == i + 1 || res == i + 2);
      s[i] = (res == i + 1) ? '1' : '0';
      BS bs;
      bs.set(i);
      bs.set(N, s[i] - '0');
      add(bs);
    }
cerr<<s<<endl;
  }
  
  // suffix
  {
    string s(N, '?');
    for (int i = N; --i >= N - (M - 1); ) {
      s[i] = '1';
      const int V = N - i + 1;
      vector<int> fail(V);
      {
        int k = fail[0] = -1;
        for (int j = 0; j < N - i; ++j) {
          for (; ~k && s[i + k] != s[i + j]; k = fail[k]) {}
          fail[j + 1] = ++k;
        }
      }
      vector<int> to[2];
      for (int e = 0; e < 2; ++e) {
        to[e].assign(V, -1);
        for (int j = 0; j <= N - i; ++j) {
          to[e][j] = (j < N - i && s[i + j] - '0' == e) ? (j + 1) : (~fail[j]) ? to[e][fail[j]] : 0;
        }
      }
      const int res = Query(V, to[0], to[1]);
      s[i] = (res == N - i) ? '1' : '0';
      BS bs;
      bs.set(i);
      bs.set(N, s[i] - '0');
      add(bs);
    }
cerr<<s<<endl;
  }
  
  // mod
  for (int m = M / 2; 2 * m >= M / 2; --m) {
    for (int r = 0; r < M; ++r) {
      BS bs;
      for (int i = r; i < N; i += m) {
        bs.set(i);
      }
      if (canAdd(bs)) {
        const int V = m << 1;
        vector<int> to[2];
        for (int e = 0; e < 2; ++e) {
          to[e].assign(m << 1, -1);
          for (int x = 0; x < m; ++x) for (int y = 0; y < 2; ++y) {
            const int xx = (x + 1 == m) ? 0 : (x + 1);
            const int yy = (x == r) ? (y ^ e) : y;
            to[e][x << 1 | y] = xx << 1 | yy;
          }
        }
        const int res = Query(V, to[0], to[1]);
        assert(res >> 1 == N % m);
        bs.set(N, res & 1);
        add(bs);
      }
    }
  }
  
  for (int i = 0; i < N; ++i) {
    assert(a[i][i]);
  }
  for (int i = N; --i >= 0; ) {
    for (int j = i + 1; j < N; ++j) if (a[i][j]) {
      if (a[j][N]) a[i].flip(N);
    }
  }
  string ans(N, '?');
  for (int i = 0; i < N; ++i) {
    ans[i] = a[i][N] ? '1' : '0';
  }
  return ans;
}