#include <bits/stdc++.h>
#include "interactive.h"
//~ #include "grader.cpp"
using namespace std;
vector <int> get(vector <int> &c){
if(c.size() == 0) return {};
auto d = get_pairwise_xor(c);
reverse(d.begin(), d.end());
while(d.size() && d.back() == 0){
d.pop_back();
}
vector <int> ret;
for(int i = 1 ; i < (int)d.size() ; i += 2){
ret.push_back(d[i]);
}
reverse(ret.begin(), ret.end());
return ret;
}
vector <int> intersect(vector <int> a, vector <int> b){
vector <int> ret;
while(a.size() && b.size()){
if(a.back() == b.back()){
ret.push_back(a.back());
a.pop_back();
b.pop_back();
}
else if(a.back() > b.back()){
a.pop_back();
}
else{
b.pop_back();
}
}
reverse(ret.begin(), ret.end());
return ret;
}
vector <int> del(vector <int> a, vector <int> b){
vector <int> ret;
while(a.size()){
if(b.size()){
if(b.back() > a.back()){
b.pop_back();
continue;
}
else if(b.back() == a.back()){
a.pop_back();
b.pop_back();
continue;
}
}
ret.push_back(a.back());
a.pop_back();
}
reverse(ret.begin(), ret.end());
return ret;
}
vector <int> guess(int n) {
vector <int> ans(n + 1);
int p = 0;
while((1 << (p + 1)) <= n){
p++;
}
ans[(1 << p) - 1] = ask((1 << p) - 1);
ans[1 << p] = ask(1 << p);
vector <vector <int> > f(10);
for(int i = 0 ; i <= p ; i++){
vector <int> all;
for(int j = 1 ; j <= n ; j++){
if((j >> i) & 1) all.push_back(j);
}
int m = i == p ? (1 << p) : (1 << p) - 1;
auto g = get(all);
all.erase(find(all.begin(), all.end(), m));
auto h = get(all);
f[i] = del(g, h);
f[i].push_back(0);
for(auto &j : f[i]) j ^= ans[m];
}
vector <int> all;
for(int i = 0 ; i < 10 ; i++){
sort(f[i].begin(), f[i].end());
for(auto &j : f[i]){
all.push_back(j);
}
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for(int i = 1 ; i <= n ; i++){
vector <int> cands = all;
for(int j = 0 ; j < 10 ; j++){
if((i >> j) & 1){
cands = intersect(cands, f[j]);
}
else{
cands = del(cands, f[j]);
}
}
ans[i] = cands[0];
}
ans.erase(ans.begin());
return ans;
}
