#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
namespace sub1{
void solve(int n){
vector<bool> vis(n + 1);
for(int i = 1; i <= n; i++){
if(!vis[i]){
Query(i);
int j = i + 1;
while(j <= n){
if(Query(j) == 1){
Answer(i, j);
vis[i] = vis[j] = true;
Query(j);
break;
}else Query(j++);
}
Query(i);
}
}
}
}
namespace sub23{
void solve(int n){
vector<int> l(n / 2), r(n / 2), ans(n / 2), a, b;
int cnt = 0;
for(int i = 1; i <= n; i++){
if(Query(i) == a.size() + 1) a.push_back(i);
else{
r[b.size()] = a.size() - 1;
b.push_back(i);
}
}
for(int i = 1; i <= n; i++) Query(i);
while(true){
bool ok = false;
vector<vector<int>> query(n / 2);
for(int i = 0; i < n / 2; i++){
if(l[i] <= r[i]){
query[(l[i] + r[i]) / 2].push_back(i);
ok = true;
}
}
if(!ok) break;
for(int i = 0; i < n / 2; i++){
Query(a[i]); //thêm a[i]
for(int j: query[i]){
if(Query(b[j]) == i + 1) ans[j] = i, r[j] = i - 1; //nếu thêm b[j] ok
else l[j] = i + 1;
Query(b[j]); //xóa b[j]
}
}
for(int i = 0; i < n / 2; i++) Query(a[i]); //xóa a[i];
}
for(int i = 0; i < n / 2; i++) Answer(b[i], a[ans[i]]);
}
}
namespace subsub{
vector<int> vis;
int cur = 0;
void banhhe(int x){
vis[x] = !vis[x];
cur = Query(x);
}
void quaylui(vector<int> a, vector<int> b){
if(a.size() == 1) Answer(a[0], b[0]);
else{
int mid = max(1, int(a.size() * 0.55));
for(int i = 0; i < mid; i++) banhhe(a[i]);
vector<int> b1, b2;
for(int i: b){
if(b1.size() == mid) b2.push_back(i);
else if(b2.size() == int(a.size()) - mid) b1.push_back(i);
else{
int pre = cur;
banhhe(i);
if(cur == pre){
if(vis[a[0]]) b1.push_back(i);
else b2.push_back(i);
}
else if(vis[a[0]]) b2.push_back(i);
else b1.push_back(i);
}
}
quaylui(vector<int>(a.begin(), a.begin() + mid), b1);
quaylui(vector<int>(a.begin() + mid, a.end()), b2);
}
}
void solve(int n){
vector<int> a, b;
vis.resize(n + 1);
for(int i = 1; i <= n; i++){
banhhe(i);
if(cur == a.size() + 1) a.push_back(i);
else b.push_back(i);
}
quaylui(a, b);
}
}
void Solve(int m){
if(m <= 100) sub1::solve(2 * m);
else if(m <= 15000) sub23::solve(2 * m);
else subsub::solve(2 * m);
}
