#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> Q;
vector<int> P;
int ans[86005];
int ON[86005];
int last;
int verdict;
int query(int x){
ON[x] ^= 1;
verdict = ON[x];
return Query(x);
}
void solve(vector<int> p, vector<int> q){
if (p.size() == 1){
Answer(q[0],p[0]);
return;
}
else if (p.size() == 2){
//printf("settle <%d,%d> <-> <%d,%d>\n",q[0],q[1],p[0],p[1]);
//printf("last query %d\n",last);
int q1;
int qon, qoff, On, Off;
if (ON[q[0]]^ON[q[1]]) {
qon = ON[q[0]]?q[0]:q[1];
qoff = ON[q[0]]?q[1]:q[0];
q1 = -1;
}
else{
q1 = query(q[0]);
qon = ON[q[0]]?q[0]:q[1];
qoff = ON[q[0]]?q[1]:q[0];
}
assert(ON[qon] && !ON[qoff]);
if (ON[p[0]] ^ ON[p[1]]){
On = ON[p[0]]?p[0]:p[1];
Off = ON[p[0]]?p[1]:p[0];
if (q1 == -1){
q1 = query(On);
if (q1 == last){
Answer(qon, On);
Answer(qoff, Off);
}
}
else if (q1 == last){
Answer(q[0],On);
Answer(q[1],Off);
}
else{
Answer(q[0],Off);
Answer(q[1],On);
}
last = q1;
return;
}
if (q1 == -1){
q1 = query(p[0]);
On = ON[p[0]]?p[0]:p[1];
Off = ON[p[0]]?p[1]:p[0];
if ((verdict == 0) ^ (q1 == last)){
Answer(qon,On);
Answer(qoff,Off);
}
else{
Answer(qoff,On);
Answer(qon,Off);
}
last = q1;
return;
}
else last = q1;
q1 = query(p[0]);
On = ON[p[0]]?p[0]:p[1];
Off = ON[p[0]]?p[1]:p[0];
if ((verdict == 0) ^ (q1 == last)){
Answer(qon,On);
Answer(qoff,Off);
}
else{
Answer(qoff,On);
Answer(qon,Off);
}
last = q1;
return;
}
#ifdef debug
for (auto x : p){
printf("%d ",x);
}
printf("<- P\n");
for (auto x : q){
printf("%d ",x);
}
printf("<- P\n");
#endif
assert(p.size() == q.size());
vector<int> Lp;
vector<int> Rp;
vector<int> Lq, Rq;
int n = q.size();
int mid = n/2;
for (auto x : q){
if (ON[x]){
if (Lq.size() == mid){
last = query(x);
Rq.push_back(x);
}
else{
Lq.push_back(x);
}
}
else{
if (Rq.size() == q.size()-mid){
last = query(x);
Lq.push_back(x);
}
else{
Rq.push_back(x);
}
}
}
for (int i = 0; i < n; i++){
int q = query(p[i]);
if (q == last){
//printf("%d goes left\n",p[i]);
Lp.push_back(p[i]);
}
else{
//printf("%d goes right\n",p[i]);
Rp.push_back(p[i]);
}
last = q;
if (Lp.size() == Lq.size() || Rp.size() == Rq.size()){
//printf("ALL FILLED\n");
for (int j = i+1; j < n; j++){
if (Lp.size() == Lq.size()) Rp.push_back(p[j]);
else Lp.push_back(p[j]);
}
break;
}
}
#ifdef debug
printf("Lp: ");
for (auto x : Lp) printf("%d ",x);
printf("\n");
printf("Rp: ");
for (auto x : Rp) printf("%d ",x);
printf("\n");
#endif
solve(Lp, Lq);
solve(Rp, Rq);
}
void Solve(int N) {
for (int i = 1; i <= 2*N; i++){
int q = query(i);
if (q == last){
Q.push_back(i);
}
else{
P.push_back(i);
}
last = q;
ON[i] = 1;
}
//srand(time(NULL));
//random_shuffle(Q.begin(),Q.end());
//random_shuffle(P.begin(),P.end());
solve(P,Q);
}
