#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 50'000;
vector<pair<int, int>> ans;
vector<int> nxtp, nxtk;
int aktr = 0;
void DC(bool czyp, bool czyk)
{
if((int)nxtp.size() == 1)
{
//cout << "A: " << nxt[0] << " " << nxt[1] << "\n";
ans.pb(make_pair(nxtp[0], nxtk[0]));
return;
}
//cout << "DC: " << nxtp.size() << " " << nxtk.size() << "\n";
int n = (int)nxtp.size();
int tr = (n + 1) / 2;
vector<int> poc = nxtp, kon = nxtk;
vector<int> lp, lk, rp, rk;
for(int i = 0; i < tr; ++i)
lp.pb(poc[i]);
for(int i = tr; i < n; ++i)
rp.pb(poc[i]);
if(czyp)
for(int i = 0; i < (int)rp.size(); ++i)
aktr = Query(rp[i]);
else
for(int i = 0; i < (int)lp.size(); ++i)
aktr = Query(lp[i]);
int prev = aktr;
if(czyk)
{
for(int i = 0; i < (int)kon.size(); ++i)
{
aktr = Query(kon[i]);
if(aktr < prev)
rk.pb(kon[i]);
else
lk.pb(kon[i]);
prev = aktr;
}
}else
{
for(int i = 0; i < (int)kon.size(); ++i)
{
aktr = Query(kon[i]);
if(aktr > prev)
rk.pb(kon[i]);
else
lk.pb(kon[i]);
prev = aktr;
}
}
nxtp = lp; nxtk = lk;
DC(1, czyk ^ 1);
nxtp = rp; nxtk = rk;
DC(0, czyk ^ 1);
}
void Solve(int _N)
{
int n = _N, prev = 0;
for(int i = 1; i <= 2 * n; ++i)
{
aktr = Query(i);
if(aktr > prev) nxtp.pb(i);
else nxtk.pb(i);
prev = aktr;
}
DC(1, 1);
for(int i = 0; i < (int)ans.size(); ++i)
Answer(ans[i].st, ans[i].nd);
}
