#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
const int prefixL = 100, sufixL = 101;
const int R = 1001;
bool prefix(int k){
int m = k+1+2;
vector<int>a(m), b(m);
for(int i=0;i<k;i++){
a[i] = i+1;
b[i] = i+1;
}
a[k] = k+1;
b[k] = k+2;
a[k+2] = k+2;
b[k+2] = k+2;
a[k+1] = k+1;
b[k+1] = k+1;
return Query(m,a,b)==(k+2);
}
string PoznajSufix(int k){
string s="2";
while((int)s.size()-1<k){
s[0]='0';
s = '2' + s;
int m = s.size();
vector<int>a(m), b(m);
vector<int>kmp(m);
kmp[0] = 0;
kmp[1] = 0;
for(int i=2;i<m;i++){
int j = kmp[i-1];
while(j!=0 && s[j+1]!=s[i])
j = kmp[j];
if(s[j+1]==s[i])
j++;
kmp[i] = j;
}
for(int i=0;i<m-1;i++){
if(s[i+1]=='0'){
a[i] = i+1;
int j = kmp[i];
while(s[j+1]!='1' && j!=0)j = kmp[j];
if(s[j+1]=='1')j++;
b[i] = j;
}
else if(s[i+1]=='1'){
int j = kmp[i];
while(s[j+1]!='0' && j!=0)j = kmp[j];
if(s[j+1]=='0')j++;
a[i] = j;
b[i] = i+1;
}
}
int j = kmp[m-1];
while(s[j+1]!='0' && j!=0)j = kmp[j];
if(s[j+1]=='0')j++;
a[m-1] = j;
j = kmp[m-1];
while(s[j+1]!='1' && j!=0)j = kmp[j];
if(s[j+1]=='1')j++;
b[m-1] = j;
if(Query(m, a, b)!=m-1)
s[1] = '1';
}
reverse(s.begin(), s.end());s.pop_back();reverse(s.begin(), s.end());
return s;
}
bool parity(int mod, int r){
int m = 2*mod;
vector<int>a(m),b(m);
for(int i=0;i<mod;i++){
if(i==r){
a[i] = (i+1)%mod;
b[i] = mod+(i+1)%mod;
}
else{
a[i] = (i+1)%mod;
b[i] = (i+1)%mod;
}
}
for(int i=0;i<mod;i++){
if(i==r){
a[i+mod] = mod+(i+1)%mod;
b[i+mod] = (i+1)%mod;
}
else{
a[i+mod] = mod+(i+1)%mod;
b[i+mod] = mod+(i+1)%mod;
}
}
return Query(m, a, b)>=mod;
}
bitset<R>gauss[R-1];
int przekotna = 0;
void dodaj(bitset<R>X){
for(int i=0;i<R-1;i++){
if(X[i]){
if(gauss[i][i]==0){
gauss[i] = X;
przekotna++;
break;
}
X^=gauss[i];
}
}
}
bool LiniowoNiezalezne(bitset<R>X){
for(int i=0;i<R-1;i++){
if(X[i]){
if(gauss[i][i]==0)return 1;
X^=gauss[i];
}
}
return 0;
}
bool odczytaj(bitset<R>X){
for(int i=0;i<R-1;i++){
if(X[i]){
X^=gauss[i];
}
}
return X[R-1];
}
string Solve(int N) {
string s;
for(int i=0;i<prefixL;i++){
bitset<R>pom;
pom[R-1] = prefix(i);
pom[i] = 1;
dodaj(pom);
//printf("%d\n", (int)pom[R-1]);
// s.push_back('0'+prefix(s.size()));
}
string sufix;
sufix = PoznajSufix(sufixL);
for(int i=N-1;i>= N-sufixL;i--){
bitset<R>pom;
pom[i] = 1;
pom[R-1] = (sufix[i-N+sufixL]-'0');
dodaj(pom);
//printf(" %d\n", (int)pom[R-1]);
}
for(int mod=1;;mod++){
for(int reszta=0;reszta<mod;reszta++){
bitset<R>pom;
for(int i=0;i<R-1;i++)
if(i%mod==reszta)
pom[i] = 1;
if(LiniowoNiezalezne(pom)){
pom[R-1] = parity(mod, reszta);
//printf("%d\n", parity(mod, reszta));
dodaj(pom);
//printf("%d %d %d\n", mod, reszta, przekotna);
//cout<<pom<<"\n";
}
if(przekotna==R-1)break;
}
if(przekotna==R-1)break;
}
for(int i=0;i<R-1;i++){
bitset<R>pom;
pom[i] = 1;
s+='0'+odczytaj(pom);
}
//cout<<s<<"\n";
return s;
}
