#include "minerals.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 86000 + 10;
const int INF = 1e9;
int n;
int min[MAXN];
int with[MAXN];
int perm[MAXN];
bool isIn[MAXN];
int taken[MAXN];
int taken0[MAXN];
int taken1[MAXN];
int taken2[MAXN];
std::vector <int> unique;
std::vector <int> second;
std::mt19937 rng(69420);
int to[MAXN];
int countDiff;
int query(int idx)
{
isIn[idx] ^= 1;
return countDiff = Query(perm[idx]);
}
void answer(int a, int b)
{
Answer(perm[a], perm[b]);
}
void Solve(int N)
{
n = N;
std::iota(perm + 1, perm + 1 + 2 * n, 1);
std::shuffle(perm + 1, perm + 1 + 2 * n, rng);
int cnt = 0;
for (int i = 1 ; i <= 2 * n ; ++i)
{
int last = countDiff;
if (unique.size() < n && (second.size() == n || query(i) > last))
{
unique.push_back(i);
} else
{
to[i] = unique.size();
second.push_back(i);
}
}
assert(unique.size() == n);
assert(second.size() == n);
int lg = 0;
while ((1 << lg + 1) < n)
{
lg++;
}
int maskFound = 0;
std::vector <int> order = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
for (int &bit : order)
{
// std::cout << " new bit: " << bit << '\n';
std::fill(taken, taken + n, 0);
std::fill(taken0, taken0 + n, 0);
std::fill(taken1, taken1 + n, 0);
std::fill(taken2, taken2 + n, 0);
std::fill(min, min + n, INF);
for (int i = 0 ; i < n ; ++i)
{
// std::cout << "prefix: " << i << ' ' << (maskFound & i) << '\n';
taken[i & maskFound]++;
taken2[i & maskFound]++;
if (i & (1 << bit)) taken1[i & maskFound]++;
else taken0[i & maskFound]++;
if (((i & (1 << bit)) > 0) != isIn[unique[i]])
{
query(unique[i]);
}
if (isIn[unique[i]])
{
min[i & maskFound] = std::min(min[i & maskFound], i);
}
}
// std::cout << "zero: " << taken[0] << ' ' << n << '\n';
for (int i = 0 ; i < n ; ++i)
{
taken[with[second[i]]]--;
if ((with[second[i]] | (1 << bit)) >= to[second[i]])
{
taken0[with[second[i]]]--;
continue;
}
if (taken1[with[second[i]]] == 0)
{
taken0[with[second[i]]]--;
continue;
}
if (taken0[with[second[i]]] == 0)
{
with[second[i]] |= (1 << bit);
taken1[with[second[i]]]--;
continue;
}
int curr = countDiff;
int next = query(second[i]);
if (curr == next)
{
taken1[with[second[i]]]--;
with[second[i]] |= (1 << bit);
} else
{
taken0[with[second[i]]]--;
}
}
maskFound |= (1 << bit);
}
for (int i = 0 ; i < n ; ++i)
{
// if (!(1 <= unique[with[second[i]]] && unique[with[second[i]]] <= 2 * n))
// {
// std::cout << "the fuck: " << second[i] << ' ' << with[second[i]] << ' ' << unique[with[second[i]]] << '\n';
// }
answer(second[i], unique[with[second[i]]]);
}
}
