#include"ancient2.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
string Solve(int n){
    string s(n,0);
    for(int i=0;i<100;++i){
        vector<int>a(i+3);
        iota(a.begin(),a.end(),1),a[i+1]=i+1,a[i+2]=i+2;
        auto b=a;b[i]=i+2,s[i]=Query(i+3,a,b)==i+1?'0':'1';
    }
    for(int i=0;i<101;++i){
        const auto gc=[&](int x){return x?s[n+x-i-1]:'0';};
        vector<int>a(i+2),b(i+2),kmp(i+1);
        for(int j=1,k=0;j<=i;++j){
            for(;k&&gc(k)!=gc(j);k=kmp[k-1]);
            kmp[j]=(k+=gc(k)==gc(j));
        }
        for(int j=0;j<i+1;++j)
            if(gc(j)=='0')a[j]=j+1,b[j]=j?b[kmp[j-1]]:0;
            else b[j]=j+1,a[j]=j?a[kmp[j-1]]:0;
        a[i+1]=a[kmp[i]],b[i+1]=b[kmp[i]];
        s[n-i-1]=Query(i+2,a,b)==i+1?'0':'1';
    }
    bitset<799>p[799];bool vs[799];fill(vs,vs+799,0);
    const auto ins=[&](bitset<799>x){
        for(int i=0;i<799;++i)if(x[i])
            if(vs[i])x^=p[i];else return p[i]=x,vs[i]=true;
        return false;
    };
    vector<bitset<800>>vec;
    for(int i=1;i<52;++i)for(int j=0;j<i;++j){
        bitset<799>bs;
        for(int k=j;k<1000;k+=i)if(k>99&&k<899)bs[k-100]=1;
        if(ins(bs)){
            vector<int>a(i*2);
            for(int k=0;k<i;++k)a[k]=k==i-1?0:k+1;
            for(int k=i;k<i*2;++k)a[k]=k==i+i-1?i:k+1;
            auto b=a;b[j]=j==i-1?i:i+j+1,b[i+j]=j==i-1?0:j+1;
            vec.emplace_back();
            vec.back()[799]=Query(i*2,a,b)>=i;
            for(int k=j;k<1000;k+=i)
                if(k>99&&k<899)vec.back()[k-100]=1;
                else if(s[k]=='1')vec.back().flip(799);
        }
    }
    for(int i=0;i<799;++i){
        int id=i;
        while(!vec[id][i])++id;swap(vec[id],vec[i]);
        for(int j=0;j<799;++j)if(i!=j&&vec[j][i])vec[j]^=vec[i];
    }
    for(int i=0;i<799;++i)s[i+100]=vec[i][799]+'0';
    return s;
}