#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz size()
using namespace std;
ll collisions(vector<ll> x);
bool ask(const vector<ll>& v, const vector<ll>& u){
vector<ll> q;
q.reserve(v.sz+u.sz);
for(auto i:v){q.pb(i);}
for(auto i:u){q.pb(i);}
return collisions(q)>0;
}
int hack(){
ll mx=(ll)(1e9);
const int b = int(sqrt(1e9)-2);
vector<ll> v,u;
for(int i = 1; i <= b; i++){
v.pb(i);
}
for(ll x = ((mx>>1)/b)*b; x <= mx+b; x+=b){
u.push_back(x);
}
while(v.sz > 1 || u.sz > 1){
if(v.sz < u.sz){
swap(v,u);
}
int mid=(v.sz>>1);
vector<ll> l(v.begin(),v.begin()+mid);
vector<ll> r(v.begin()+mid,v.end());
if(ask(l,u)){
v.swap(l);
}else{
v.swap(r);
}
}
return llabs(v[0]-u[0]);
}
