#include "hack.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
int hack(){
int l = 5e8, r = 1e9;
int X = -1;
while(l <= r){
int mid = l + r >> 1;
int b = sqrt(mid - l + 1);
vector<ll> v;
for(int i = 1;i<=b;++i) v.pb(i);
for(int i = l + b;i<=mid;i += b) v.pb(i);
v.pb(mid + 1);
if(collisions(v)) r = mid - 1, X = mid;
else l = mid + 1;
}
assert(~X);
int FX = X;
for(int i = 2;i * i<=FX;++i){
if(FX%i == 0){
while(FX % i == 0) FX /= i;
while(X % i == 0 and collisions(vector<ll>{1, X / i + 1})) X /= i;
}
}
while(FX > 1 and X > FX and collisions(vector<ll>{1, X / FX + 1})) X /= FX;
return X;
}
