#include "ancient2.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int MAXN = 1000;
struct equation
{
bitset<MAXN> eq;
void operator^=(const equation& other)
{
eq ^= other.eq;
}
};
int n;
equation eq[MAXN];
bool is_used[MAXN];
int eq_count = 0;
bool add_eq(equation new_eq, bool check = false)
{
rep(i,n)
{
if(new_eq.eq[i] == 1)
{
if(!is_used[i])
{
if(!check)
{
eq[i] = new_eq;
is_used[i] = 1;
eq_count++;
}
// if(!check) cout << "git\n";
return 1;
}
new_eq ^= eq[i];
}
}
//cout << "boo\n";
return false;
}
string get_ans()
{
vi ans(n,0);
for(int i = n-1; i >= 0; i--)
{
int sum = eq[i].eq[n];
for(int j = i+1; j < n; j++)
{
sum ^= (eq[i].eq[j]*ans[j]);
}
ans[i] = sum;
}
string ans_str;
rep(i,n) ans_str += (char)('0' + ans[i]);
return ans_str;
}
void get_eq_kth(int x, int mod)
{
equation ans;
for(int i = mod; i < n; i += x)
{
// cout << i << " i\n";
ans.eq[i] = 1;
}
if(!add_eq(ans,true)) return;
int m = x*2;
vi a(m);
vi b(m);
// cout << mod << " mod\n";
for(int i = 0; i < x*2; i += 2)
{
if(i/2 == mod)
{
a[i] = (i+2)%(x*2);
b[i] = (i+3)%(x*2);
a[i+1] = (i+3)%(x*2);
b[i+1] = (i+2)%(x*2);
}
else
{
a[i] = (i+2)%(x*2);
b[i] = (i+2)%(x*2);
a[i+1] = (i+3)%(x*2);
b[i+1] = (i+3)%(x*2);
}
}
int q = Query(m,a,b);
if(q % 2 == 1)
{
ans.eq[n] = 1;
}
add_eq(ans);
}
equation get_first_num(int x)
{
equation ans;
ans.eq[x] = 1;
int m = x+3;
vi a(m);
vi b(m);
rep(i,x)
{
a[i] = i+1;
b[i] = i+1;
}
a[x] = m-2;
b[x] = m-1;
a[m-1] = m-1;
b[m-1] = m-1;
a[m-2] = m-2;
b[m-2] = m-2;
int q = Query(m,a,b);
// cout << q << " q\n";
if(q == m-1) ans.eq[n] = 1;
return ans;
}
int find_max_suf(string s, string suf)
{
string s1,s2;
int n = siz(suf);
int ans = 0;
rep(i,n)
{
s1 += s[i];
s2 = suf[n-1-i] + s2;
if(s1 == s2) ans = max(ans,i+1);
}
return ans;
}
bool is_sufix(string suf)
{
int m = siz(suf)+1;
vi a(m);
vi b(m);
string cur_suf;
rep(i,m)
{
a[i] = find_max_suf(suf,cur_suf + "0");
b[i] = find_max_suf(suf,cur_suf + "1");
if(i != siz(suf)) cur_suf += suf[i];
}
int x = Query(m,a,b);
if(x == m-1) return true;
return false;
}
string Solve(int N)
{
n = N;
rep(i,100)
{
add_eq(get_first_num(i));
if(eq_count == n) return get_ans();
}
string cur_suf = "";
rep(k,100)
{
//cout << cur_suf << " suf\n";
if(is_sufix("0" + cur_suf))
{
equation eq;
eq.eq[n-k-1] = 1;
add_eq(eq);
cur_suf = '0' + cur_suf;
}
else
{
equation eq;
eq.eq[n-k-1] = 1;
eq.eq[n] = 1;
add_eq(eq);
cur_suf = '1' + cur_suf;
}
if(eq_count == n) return get_ans();
}
rep2(k,1,1000)
{
rep(mod,k)
{
get_eq_kth(k,mod);
if(eq_count == n) return get_ans();
}
}
}
