#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, int l, int r){
if (r == l){
Answer(Q[l],p[0]);
return;
}
else if (l + 1 == r){
//printf("settle <%d,%d> <-> <%d,%d>\n",Q[l],Q[r],p[0],p[1]);
//printf("last query %d\n",last);
int q1;
int qon, qoff, On, Off;
if (ON[Q[l]]^ON[Q[r]]) {
qon = ON[Q[l]]?Q[l]:Q[r];
qoff = ON[Q[l]]?Q[r]:Q[l];
q1 = -1;
}
else{
q1 = query(Q[l]);
qon = ON[Q[l]]?Q[l]:Q[r];
qoff = ON[Q[l]]?Q[r]:Q[l];
}
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[l],On);
Answer(Q[r],Off);
}
else{
Answer(Q[l],Off);
Answer(Q[r],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
printf("new <%d,%d>\n",l,r);
for (auto x : p){
printf("%d ",x);
}
printf("<- P\n");
for (int i = l; i <= r; i++){
printf("%d ",Q[i]);
}
printf("<- Q\n");
#endif
//assert(p.size() == r-l+1);
vector<int> Lp;
vector<int> Rp;
int n = r-l+1;
int mid;
mid = (l+r)/2;
int Lon, Loff, Ron, Roff, Ls = l, Le = mid, Rs = mid+1, Re = r;
for (int i = l; i <= mid; i++){
Lon += ON[Q[i]];
Loff += 1-ON[Q[i]];
}
for (int i = mid+1; i <= r; i++){
Ron += ON[Q[i]];
Roff += 1-ON[Q[i]];
}
if (Lon+Roff < Loff+Ron){
swap(Ls,Rs);
swap(Le,Re);
}
//printf("decided to on <%d - %d>, off <%d - %d>\n",Ls,Le,Rs,Re);
for (int i = Ls; i <= Le; i++){
if (!ON[Q[i]]){
last= query(Q[i]);
}
}
for (int i = Rs; i <= Re; i++){
if (ON[Q[i]]){
last= query(Q[i]);
}
}
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() == Le-Ls+1 || Rp.size() == Re-Rs+1){
//printf("ALL FILLED\n");
for (int j = i+1; j < n; j++){
if (Lp.size() == Le-Ls+1) 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, Ls, Le);
solve(Rp, Rs, Re);
}
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,0,N-1);
}
