#include "ancient2.h"
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
std::string Solve(int N) {
// query one bit:
// a[i], b[i] = i+1
// a[b] = 1000
// b[b] = 1001
// a,b[1000] = 1000
// a,b[1001] = 1001
int Np = 500;
std::vector<int> a(Np+2);
std::iota(a.begin(),a.begin()+Np,1);
a[Np] = Np;
a[Np+1] = Np+1;
auto b = a;
std::string s;
std::string sb;
for(int i = 0; i < Np; i++)
{
a[i] = Np;
b[i] = Np+1;
s.push_back((Query(Np+2,a,b)>Np) ? '1' : '0');
a[i] = i+1;
b[i] = i+1;
}
a[-1+Np/2] = 0;
b[-1+Np/2] = 0;
a[Np-1] = Np/2;
b[Np-1] = Np/2;
for(int i = Np; i < Np + (Np/2); i++)
{
auto f = Np/2;
// query xor of bits in residue class
b[i%f] = f+(1+i)%f;
b[f+(i%f)] = (1+i)%f;
s.push_back((Query(a.size(),a,b)>=f ? '1' : '0'));
b[i%f] = (1+i)%f;
b[f+(i%f)] = f+(1+i)%f;
}
for(int i = Np+(Np/2); i < N; i++)
{
auto f = Np/2;
b[i%f] = f + ((1+i)%f);
a[f+(i%f)] = (i+1)%f;
s.push_back((Query(a.size(),a,b)>=f ? '1' : '0'));
b[i%f] = ((1+i)%f);
a[f+(i%f)] = f + ((1+i)%f);
}
for(int i = 0; i < 250; i++)
{
s[500+i] = ((s[i]=='1') ^ (s[250+i]=='1') ^ (s[500+i]=='1') ^ (s[750+i]=='1')) ? '1' : '0';
}
return s;
// now know last 50 bits
// use that information somehow
// can query xor of arithmetic sequences (up to 50 long)
// count how many 1's
}
