#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 5e3+10, K = 52, MX = 30;
namespace {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
vector<bool> done;
void answer(int x, int y){
if(done[x] || done[y]) return;
done[x] = done[y] = 1;
cerr << x << ' ' << y << '\n';
Answer(x, y);
}
int query(int l, int r, int other){
vi v;
for(int j = l; j <= r; ++j) v.pb(j);
v.pb(other);
return Query(v);
}
int query2(int l, int r, int other, int other2){
vi v;
for(int j = l; j <= r; ++j) v.pb(j);
v.pb(other);
if(other2 < l || r < other2)
v.pb(other2);
return Query(v);
}
}
void Solve(int n) {
vi go(2*n+1);
done.resize(2*n + 1);
for(int i = n + 1; i <= 2*n; ++i){
int last = n;
vi S;
for(int rep = 0; rep < 3; ++rep){
int l = 1, r = last, res = -1;
while(l <= r){
int mid = l+r>>1;
if(query(mid, r, i) < r - mid + 2){ // it contains smth
res = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
if(res == -1) break;
S.pb(res);
last = res - 1;
}
// for(int x: S) cerr << x << ' ';
// cerr << i << '\n';
if(S.size() == 1){
answer(i, S[0]);
}else{
vi A = {S[0], S[1], i};
vi B = {S[1], S[2], i};
vi C = {S[0], S[2], i};
vector<vi> order;
order.pb(A);
order.pb(B);
order.pb(C);
for(int i = 0; i < 3; ++i) order[i].swap(order[rn(0, i)]);
// randomize this order to save up half the queries (around 1.5N)
for(int j = 0; j < 3; ++j){
if(Query(order[j]) == 1){
if(order[j] == A) go[S[2]] = i;
if(order[j] == B) go[S[0]] = i;
if(order[j] == C) go[S[1]] = i;
break;
}
}
// int a = Query(A);
// int b = Query(B);
// int c = Query(C);
// if(a == 1) go[S[2]] = i;
// else if(b == 1) go[S[0]] = i;
// else go[S[1]] = i; // a male is loved by which female
}
}
// for(int i= 1; i <= n; ++i) cerr << go[i] << '\n';
for(int i = 1; i <= n; ++i){
if(done[i]) continue;
if(go[i] == 0){
// only one
int l = n + 1, r = 2 * n, res = -1;
while(l <= r){
int mid = l+r>>1;
if(query(mid, r, i) < r - mid + 2){ // it contains smth
res = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
answer(i, res);
continue;
}
int x = rn(0, 1);
// randomize whether searching from right or left
if(x == 0){
int l = n + 1, r = 2*n, res = -1;
while(l <= r){
int mid = l+r>>1;
// cerr << l << ' ' << mid << ' ' << i << ' ' << go[i] << '\n';
// cerr << query2(l, mid, i, go[i]) << '\n';
int sz = mid - l + 1 + (l <= go[i] && go[i] <= mid ? -1 : 0);
if(query2(l, mid, i, go[i]) == sz){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
// cerr << i << ' ' << res << '\n';
// the point we found might be either the one that is equal with this male, or it's the one male loves
assert(res != -1);
vi p = {i, go[i], res};
int a = Query(p);
if(a == 1){
answer(i, res); // we found it, yea
}else{
// we gotta search n + 1 .... res - 1
l = n + 1, r = res - 1;
while(l <= r){
int mid = l+r>>1;
int sz = mid - l + 1 - (l <= go[i] && go[i] <= mid ? -1 : 0);
if(query2(l, mid, i, go[i]) == sz){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
answer(i, res);
}
}else{
int l = n + 1, r = 2*n, res = -1;
while(l <= r){
int mid = l+r>>1;
int sz = r - mid + 1 + (mid <= go[i] && go[i] <= r ? -1 : 0);
if(query2(mid, r, i, go[i]) == sz){
res = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
// the point we found might be either the one that is equal with this male, or it's the one male loves
assert(res != -1);
vi p = {i, go[i], res};
int a = Query(p);
if(a == 1){
answer(i, res); // we found it, yea
}else{
// we gotta search res + 1 .... 2 * n
l = res + 1, r = 2 * n;
while(l <= r){
int mid = l+r>>1;
int sz = r - mid + 1 + (mid <= go[i] && go[i] <= r ? -1 : 0);
if(query2(mid, r, i, go[i]) == sz){
res = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
answer(i, res);
}
}
}
// vector<vi> S(2*n+1);
// done.resize(2*n+1);
// vector<int> v, go(n*2+1);
// for(int i = 1; i <= 2*n; ++i) v.pb(i);
// for(int i = 1; i <= n*2; ++i){
// for(int j = 1; j <= n*2; ++j){
// if(i != j){
// vi p; p.pb(i);
// p.pb(j);
// int x = Query(p);
// if(x == 1){
// S[i].pb(j);
// }
// }
// }
// }
// for(int i = 1; i <= 2*n; ++i){
// for(int x: S[i]){
// if(go[i] != x && go[x] != i){
// answer(i, x);
// }
// }
// }
}
