#include "ancient2.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int n;
int mQuery(int m, vector<int>&a, vector<int>&b){
/*cout<<m<<endl;
for(auto e: a){
cout<<e<<" ";
}
cout<<endl;
for(auto e: b){
cout<<e<<" ";
}
cout<<endl;*/
int r= Query(m, a, b);
//cout<<"res "<<r<<endl
return r;
}
const int SZ = 700;
map<int, int> simulate(vector<pii>& a, vector<pii>& b, int start, string s){
int pos = start;
vector<int> oc(SZ);
for(int i = 0; i<1000; i++){
if(s[i] == '0'){
pos = a[pos].second;
}
else{
pos =b[pos].second;
}
oc[pos]++;
}
cout<<oc[start]<<" "<<oc[pos]<<endl;
map<int, int> nb;
for(int i = 0; i<SZ; i++){
nb[oc[i]]++;
}
return nb;
}
void add_key_check(vector<int>& a, vector<int>& b, string key){
int begin = a.size()-1;
vector<vector<int>> ids;
ids.resize(2, vector<int>(key.size()));
a.resize(a.size()+2*key.size());
b.resize(b.size()+2*key.size());
for(int i = 0; i<key.size()-1; i++){
if(key[i] == '0'){
a[begin+i] = begin+i+1;
b[begin+i] = begin+key.size()+i;
}
else{
b[begin+i] = begin+i+1;
a[begin+i] = begin+key.size()+i;
}
}
}
void add_choice(vector<int>& a, vector<int>& b){
int begin = a.size()-1;
a.back() = begin+1;
b.back() = begin+2;
for(int i = 1; i<=2; i++){
a.push_back(i+begin);
b.push_back(i+begin);
}
}
void add_double_choice(vector<int>& a, vector<int>& b){
int begin = a.size()-1;
//cout<<"begin is "<<begin<<endl;
a.resize(a.size()+6);
b.resize(b.size()+6);
for(int i =1; i<4; i++){
a[i+begin-1] = begin + 2*i -1;
b[i+begin-1] = begin + 2*i ;
}
for(int i = 4; i<8; i++){
a[i+begin-1] = i+begin-1;
b[i+begin-1] = i+begin-1;
}
}
const ll mod = 1e9 +7;
int oc[2] = {0, 0};
int chines_remainders(int a, int ma, int b, int mb){
a =a%ma;
b= b%mb;
for(int i = 0; i<=1000; i++){
if(i%ma == a && i%mb ==b){
return i;
}
}
//cout<<a<<" "<<b<<endl;
}
void find_oc(){
vector<int> a, b;
for(int i = 0; i<31; i++){
a.push_back(i);
b.push_back((i+1)%31);
}
int m31 = mQuery(a.size(), a, b);
a.clear();
b.clear();
for(int i = 0; i<37; i++){
a.push_back(i);
b.push_back((i+1)%37);
}
int m37 = mQuery(a.size(), a, b);
oc[1] = chines_remainders(m31, 31, m37, 37);
oc[0] = n-oc[1];
}
int find_remaining(vector<vector<int>>& v){
auto v1 = v;
int begin = v[0].size()-1;
v[0].resize(v[0].size()+30);
v[1].resize(v[1].size()+30);
for(int i = 0; i<31; i++){
v[0][i+begin] =begin +((i+1)%31);
v[1][i+begin] =begin +((i+1)%31);
}
int m31 = mQuery(v[0].size(), v[0], v[1])-begin+1;
swap(v, v1);
v[0].resize(v[0].size()+36);
v[1].resize(v[1].size()+36);
for(int i = 0; i<37; i++){
v[0][i+begin] =begin +((i+1)%37);
v[1][i+begin] =begin +((i+1)%37);
}
int m37 = mQuery(v[0].size(), v[0], v[1])-begin+1;
return chines_remainders(m31, 31, m37, 37);
}
void add_delay(int citizen, int len, vector<vector<int>>& v){
int exc = (citizen+1)%2;
for(int i = 0; i<len; i++){
v[citizen].push_back(i+1);
v[exc].push_back(i);
}
}
int find_dist(vector<vector<int>>& v, int citizen){
auto v1 = v;
int exc= (citizen+1)%2;
int begin = v[0].size()-1;
v[0].resize(v[0].size()+61);
v[1].resize(v[1].size()+61);
for(int i = 0; i<31; i++){
v[exc][2*i+begin] =begin +((2*i+2)%62);
v[citizen][2*i+begin] =begin +((2*i+1)%62);
v[exc][2*i+1+begin] = 2*i+1+begin;
v[citizen][2*i+1+begin] = 2*i+1+begin;
}
int m31 = (mQuery(v[0].size(), v[0], v[1])-begin+1)/2;
swap(v, v1);
v[0].resize(v[0].size()+73);
v[1].resize(v[1].size()+73);
for(int i = 0; i<37; i++){
v[exc][2*i+begin] =begin +((2*i+2)%74);
v[citizen][2*i+begin] =begin +((2*i+1)%74);
v[exc][2*i+1+begin] = 2*i+1+begin;
v[citizen][2*i+1+begin] = 2*i+1+begin;
}
int m37 = (mQuery(v[0].size(), v[0], v[1])-begin+1)/2;
return chines_remainders(m31, 31, m37, 37);
}
std::string Solve(int N) {
n= N;
srand(time(NULL));
find_oc();
vector<int> citizen_pos;
int citizen= 0;
if(oc[0]>oc[1]){
citizen = 1;
}
string s(n, (char)('0'+((citizen+1)%2)));
//cout<<oc[0]<<" "<<oc[1]<<endl;
if(oc[citizen]<500){
//cout<<oc[citizen]<<endl;
vector<vector<int>> v(2);
add_delay(citizen,2, v);
citizen_pos.push_back(n-find_remaining(v));
for(int i = 1; i<oc[citizen]; i++){
vector<vector<int>> v(2);
add_delay(citizen, i+1, v);
citizen_pos.push_back(citizen_pos.back()+find_dist(v, citizen));
}
for(auto e: citizen_pos){
//cout<<e<<endl;
s[e]= (char)('0'+citizen);
}
}
else{
vector<int> pref_oc(2, 0);
for(int i = 0; i<n; i++){
vector<vector<int>> v(2);
if(i>0){
add_delay(s[i-1]-'0', pref_oc[s[i-1]-'0']+1, v);
}
else{
v[0].push_back(0);
v[1].push_back(1);
}
if(i<n-1){
int base= v[0].size()-1;
add_double_choice(v[0], v[1]);
int r= mQuery(v[0].size(), v[0], v[1])-base+1;
//cout<<r<<endl;
for(int j = 1; j>=0; j--){
s[i+j] = (char)('0'+(r%2));
pref_oc[s[i+j]-'0']++;
r/=2;
}
//cout<<s<<endl;
i++;
}
else{
add_choice(v[0], v[1]);
int r= mQuery(v[0].size(), v[0], v[1]);
if(r== v[0].size()-1){
s[i] ='1';
pref_oc[1]++;
}
else{
s[i] = '0';
pref_oc[0]++;
}
}
}
}
//cout<<s<<endl;
return s;
}
