#include "minerals.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
const int N = 43005;
int cost[N], best[N], cur = 0;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void Prepare() {
cost[2] = 2; best[2] = 1;
for (int i = 3; i < N; i++) {
int j = best[i - 1];
if (cost[i - j - 1] + cost[j + 1] +
j + 1 < cost[i - j] + cost[j] + j) j++;
cost[i] = cost[i - j] + cost[j] + j + i;
best[i] = j;
}
}
void Split(vector<int> x, vector<int> y, bool f) {
if (x.size() == 2) {
cur = Query(x[f]);
int nxt = Query(y[0]);
if (cur != nxt) {
Answer(x[0], y[0]);
Answer(x[1], y[1]);
} else {
Answer(x[0], y[1]);
Answer(x[1], y[0]);
}
cur = nxt; return;
}
if (x.size() == 1)
return Answer(x[0], y[0]);
int n = x.size(), len = best[n];
vector<int> nx[2], ny[2];
for (int i = 0; i < len; i++) {
nx[f ^ 1].push_back(x[i]);
cur = Query(x[i]);
}
for (int i = len; i < n; i++)
nx[f].push_back(x[i]);
shuffle(y.begin(), y.end(), rng);
for (int i = 0; i < n; i++) {
if (nx[0].size() == ny[0].size())
ny[1].push_back(y[i]);
else if (nx[1].size() == ny[1].size())
ny[0].push_back(y[i]);
else {
int nxt = Query(y[i]);
if (cur != nxt)
ny[1].push_back(y[i]);
else ny[0].push_back(y[i]);
cur = nxt;
}
}
Split(nx[0], ny[0], 0);
Split(nx[1], ny[1], 1);
}
}
void Solve(int n) {
Prepare(); vector<int> x, y;
for (int i = 1; i <= 2 * n; i++) {
int nxt = Query(i);
if (nxt != cur) x.push_back(i);
else y.push_back(i);
cur = nxt;
}
cerr<<cost[43000];
Split(x, y, 0);
}
