#include "minerals.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
struct API{
set<ll> ins; ll val, n;
vector<ll> perm;
API(int N){
val=-1; n=N;
for (ll i=0; i<n; i++) perm.push_back(i);
shuffle(perm.begin(), perm.end(), rnd);
}
ll getind(ll ind){
return perm[ind-1]+1;
}
bool status(ll ind){
ind=getind(ind);
return ins.count(ind)>0;
}
void in(ll ind){
ind=getind(ind);
if (ins.count(ind)) return;
val=Query(ind); ins.insert(ind);
}
void out(ll ind){
ind=getind(ind);
if (!ins.count(ind)) return;
val=Query(ind); ins.erase(ind);
}
ll get(){
return val;
}
// void debug(){
// for (auto x:ins)
// }
};
int n;
void Solve(int N) {
n=2*N; API com(2*N);
vector<ll> a, b; int tmp=-1;
for (ll i=1; i<=n; i++){
com.in(i);
int ntmp = com.get();
if (ntmp!=tmp){
a.push_back(i);
}else{
b.push_back(i);
}
tmp=ntmp;
}
vector<pair<vector<ll>, vector<ll>>> search, nsearch;
vector<pair<ll, ll>> res;
search.push_back({a, b});
while (!search.empty()){
set<ll> swps;
for (auto &[sa, sb]:search){
// {
// for (auto x:sa) cout << x << " ";
// cout << endl;
// for (auto x:sb) cout << x << " ";
// cout << endl << endl;
// }
assert(sa.size()==sb.size());
if (sa.size()==1){
res.push_back({com.getind(sa[0]), com.getind(sb[0])}); continue;
}
ll sz=sa.size(), complex=0, complex2=0;
for (ll i=0; i<sz/2; i++){
if (!com.status(sa[i])) complex++;
// com.in(sa[i]);
}
for (ll i=sz/2; i<sz; i++){
if (com.status(sa[i])) complex++;
// com.out(sa[i]);
}
for (ll i=0; i<sz/2; i++){
if (com.status(sa[i])) complex2++;
// com.in(sa[i]);
}
for (ll i=sz/2; i<sz; i++){
if (!com.status(sa[i])) complex2++;
// com.out(sa[i]);
}
if (complex<complex2){
for (ll i=0; i<sz/2; i++){
com.in(sa[i]);
}
for (ll i=sz/2; i<sz; i++){
com.out(sa[i]);
}
}else{
for (ll i=0; i<sz/2; i++){
com.out(sa[i]);
}
for (ll i=sz/2; i<sz; i++){
com.in(sa[i]);
}
swps.insert(sa[0]);
}
}
nsearch.clear();
for (auto &[sa, sb]:search){
if (sa.size()==1) continue;
vector<ll> left1, right1, left2, right2;
ll sz=sa.size();
for (ll i=0; i<sz/2; i++){
left1.push_back(sa[i]);
}
for (ll i=sz/2; i<sz; i++){
right1.push_back(sa[i]);
}
for (ll i=0; i<(ll)sb.size()-1; i++){
ll x=sb[i];
ll prev=com.get();
if (com.status(x)){
com.out(x);
}else{
com.in(x);
}
ll cur = com.get();
if (prev==cur) {
if (swps.count(sa[0])) right2.push_back(x);
else left2.push_back(x);
} else {
if (!swps.count(sa[0])) right2.push_back(x);
else left2.push_back(x);
}
if (left1.size()==left2.size()){
for (ll j=i+1; j<(ll)sb.size()-1; j++) right2.push_back(sb[j]);
break;
}else if (right1.size()==right2.size()){
for (ll j=i+1; j<(ll)sb.size()-1; j++) left2.push_back(sb[j]);
break;
}
}
if (left2.size()<right2.size()) left2.push_back(sb.back());
else right2.push_back(sb.back());
nsearch.push_back({left1, left2});
nsearch.push_back({right1, right2});
}
swap(search, nsearch);
}
for (auto [x, y]:res) Answer(x, y);
}
