#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
const int mxN = 1500;
ll n;
random_device rd;
mt19937_64 gen(rd());
ll query(ll x, ll y, vector<ll> v){
if(x > y) swap(x, y);
// cout << x << ' ' << y << '\n';
// cout << " --> ";
// for(auto it : v) cout << it << ' ';
// cout << endl;
int place[n];
for(int i = 0; i < n; i++) place[i] = 0;
for(auto it : v) place[it] = 1;
return Ask(x, y, place);
}
void ans(ll x, ll y){
if(x > y) swap(x, y);
// cout << x << ' ' << y << endl;
Answer(x, y);
}
void f(vector<ll> v){
// cout << " ------> ";
// for(auto it : v) cout << it << ' ';
// cout << endl;
ll sz = v.size();
if(sz == 1) return;
if(sz == 2){
ans(v[0], v[1]);
return;
}
vector<bool> vis(n, false);
uniform_int_distribution<ll> dis(0, sz - 1);
ll at = v[dis(gen)],sz1 = 0;
vector<vector<ll>> v1;
for(auto it : v){
if(it == at) continue;
if(query(at, it, {at, it})){
ans(at, it);
v1.pb({it});
vis[it] = true;
sz1++;
}
}
for(auto it : v){
if(it == at or vis[it]) continue;
ll l = -1,r = sz1 - 1;
while(r > l + 1){
vector<ll> vv;
for(auto i : v) if(!vis[i]) vv.pb(i);
ll mid = l + (r - l) / 2;
for(int i = 0; i <= mid; i++) vv.pb(v1[i][0]);
if(query(it, at, vv)) r = mid;
else l = mid;
}
v1[r].pb(it);
}
// cout << " --> " << sz1 << endl;
for(int i = 0; i < sz1; i++){
f(v1[i]);
}
}
void Detect(int T, int N) {
n = N;
vector<ll> v;
for(int i = 0; i < n; i++) v.pb(i);
f(v);
return;
}
