#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> dist(1,1000000000);
int hack(){
vector<ll> x;
int l=1,r=65536,m=(l+r)/2;
ll ret;
int query=0;
while(l<r){
ll cur=1;
x.pb(cur);
for(ll i=1;i<=m;i++){
cur+=i;
x.pb(cur);
}
ret=collisions(x);
query+=x.size();
// cerr<<query<<' '<<m<<endl;
if(ret)r=m;
else l=m+1;
m=(l+r)/2;
x.clear();
}
vector<ll> tmp;
ll cur=1;
tmp.pb(cur);
for(ll i=1;i<=m;i++){
cur+=i;
tmp.pb(cur);
}
int n=tmp.size();
// for(auto i:tmp)cerr<<i<<' ';
// cerr<<endl;
for(int i=n-2;i>=0;i--){
x.pb(tmp[i]);
x.pb(tmp.back());
ret=collisions(x);
if(ret){
return tmp.back()-tmp[i];
}
x.clear();
}
return 1000000000;
}
