#include "hack.h"
#include "bits/stdc++.h"
#define pb push_back
#define dbg(X) cerr<<#X<<": "<<X<<endl
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;
using ll = long long;
ll n;
mt19937_64 rng(time(0));
ll rnd(ll l,ll r){return uniform_int_distribution<ll>(l,r)(rng);}
map<ll,bool> tu;
vector<ll> v,w;
ll mx = 1000000000;
/**
1
1000000000
**/
int hack(){
ll m = 10000;
ll c = -1;
if(collisions({1,2})) return 1;
ll mxv = 100*mx;
while(1){
v.clear(); tu.clear();
for(ll i = 0;i<m;i++){
ll x = rnd(1,mxv);
if(tu[x]) i--;
else{
v.pb(x);
tu[x] = 1;
}
}
ll cnt = collisions(v);
if(cnt==0) continue;
ll tl = 0,tr = m-1,mid,rez;
while(tl<=tr){
mid = (tl+tr)/2;
w.clear();
for(ll i = 0;i<=mid;i++) w.pb(v[i]);
if(collisions(w)) rez = mid,tr = mid-1;
else tl = mid+1;
}
ll R = rez;
tl = 0,tr = R,rez = -1;
while(tl<=tr){
mid = (tl+tr)/2;
w.clear();
for(ll i = mid;i<=R;i++) w.pb(v[i]);
if(collisions(w)) rez = mid,tl = mid+1;
else tr = mid-1;
}
ll L = rez;
c = abs(v[L]-v[R]);
break;
}
ll ans = c;
for(ll i = 2;i*i<=c;i++){
if(c%i==0){
//dbg(i);
if(collisions({1,i+1})) ans = min(ans,i);
if(i*i!=c){
//dbg(c/i);
if(collisions({1,c/i+1})) ans = min(ans,c/i);
}
}
}
return ans ;
}
