#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
int half_n, n;
namespace sub1{
void solve(){
vector<bool>vis(n + 1, false);
for(int i = 1; i <= n; i++){
if(!vis[i]){
Query(i);
for(int j = i + 1; j <= n; Query(j++)){
if(Query(j) == 1){
Answer(i, j);
vis[i] = vis[j] = true;
Query(j);
break;
}
}
Query(i);
}
}
}
}
namespace sub23{
void solve(){
vector<int>a, b, low(half_n, 0), high(half_n), ans(half_n);
for(int i = 1, pre = 0; i <= n; i++){
if(Query(i) == pre + 1){
pre++;
a.push_back(i);
}
else{
high[b.size()] = int(a.size()) - 1;
b.push_back(i);
Query(i);
}
}
for(bool start_0 = false; true; start_0 ^= 1){
bool have = false;
vector<vector<int>>query(half_n);
for(int i = 0; i < half_n; i++){
if(low[i] <= high[i]){
query[(low[i] + high[i]) >> 1].push_back(i);
have = true;
}
}
if(!have){
break;
}
if(start_0){
for(int i = 0; i < half_n; i++){
Query(a[i]);
for(int& j : query[i]){
if(Query(b[j]) == i + 1){
high[j] = (ans[j] = i) - 1;
}
else{
low[j] = i + 1;
}
Query(b[j]);
}
}
}
else{
for(int i = half_n - 1; i > -1; Query(a[i--])){
for(int& j : query[i]){
if(Query(b[j]) == i + 1){
high[j] = (ans[j] = i) - 1;
}
else{
low[j] = i + 1;
}
Query(b[j]);
}
}
}
}
for(int i = 0; i < half_n; i++){
Answer(b[i], a[ans[i]]);
}
}
}
const int lim = 43005;
const int INF = 1e9;
bitset<lim << 1>vis;
int cur = 0;
void toggle(int x){
vis[x] = !vis[x];
cur = Query(x);
}
namespace sub45{
void solve(){
vis.reset();
vector<int>a, b;
for(int i = 1; i <= n; i++){
toggle(i);
if(cur == a.size() + 1){
a.push_back(i);
}
else{
b.push_back(i);
}
}
int LG = 0;
while((1 << LG) < half_n){
LG++;
}
vector<vector<int>>dp(LG, vector<int>(2, INF)), trace(LG, vector<int>(2, -1));
for(int i = dp[0][0] = dp[0][1] = 0; i < half_n; i++){
dp[0][(i & 1) ^ 1]++;
}
for(int bit = 1; bit < LG; bit++){
for(int p = 0; p < 2; p++){
for(int c = 0; c < 2; c++){
int val = dp[bit - 1][p];
for(int i = 0; i < half_n; i++){
if(((i >> bit & 1) == c && (i >> (bit - 1) & 1) != p) || ((i >> bit & 1) != c && (i >> (bit - 1) & 1) == p)){
val++;
}
}
if(minimize(dp[bit][c], val)){
trace[bit][c] = p;
}
}
}
}
vector<bool>z(LG);
for(int i = LG - 1, s = dp[i][1] < dp[i][0]; i > -1; s = trace[i--][s]){
z[i] = s;
}
vector<int>ans(half_n, 0);
for(int bit = 0; bit < LG; bit++){
for(int i = 0; i < half_n; i++){
if((vis[a[i]] && (i >> bit & 1) != z[bit]) || (!vis[a[i]] && (i >> bit & 1) == z[bit])){
toggle(a[i]);
}
}
for(int i = 0; i < half_n; i++){
if((ans[i] | (1 << bit)) >= half_n){
continue;
}
int pre = cur;
toggle(b[i]);
if((z[bit] && cur == pre) || (!z[bit] && cur != pre)){
ans[i] |= 1 << bit;
}
}
}
for(int i = 0; i < half_n; i++){
Answer(b[i], a[ans[i]]);
}
}
}
namespace sub6789{
void play(vector<int>a, vector<int>b){
if(a.size() == 1){
Answer(a[0], b[0]);
return;
}
int m = max(1, int(a.size() * 0.38));
for(int i = 0; i < m; i++){
toggle(a[i]);
}
vector<int>b1, b2;
for(int& i : b){
if(b1.size() == m){
b2.push_back(i);
}
else if(b2.size() == int(a.size()) - m){
b1.push_back(i);
}
else{
int pre = cur;
toggle(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);
}
}
}
play(vector<int>(a.begin(), a.begin() + m), b1);
play(vector<int>(a.begin() + m, a.end()), b2);
}
void solve(){
vis.reset();
vector<int>a, b;
for(int i = 1; i <= n; i++){
toggle(i);
if(cur == a.size() + 1){
a.push_back(i);
}
else{
b.push_back(i);
}
}
play(a, b);
}
}
void Solve(int _n){
n = (half_n = _n) << 1;
if(half_n <= 100){
sub1::solve();
}
else if(half_n <= 15000){
sub23::solve();
}
else if(half_n <= 39000){
sub45::solve();
}
else{
sub6789::solve();
}
}
