#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) (int)(lower_bound(all(v),i)-v.begin())
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
ll big = 1e9;
ll piv = 10;
double r = 2;
bool chk(ll s, ll a){
vector<ll> v;
forf(i,1,a) v.pb(i);
forf(i,1,a) v.pb(s+i*a);
return collisions(v);
}
ll dnc(ll s, ll e){
if(e-s <= piv){
forf(i,s,e){
vector<ll> v;
v.pb(1), v.pb(i+1);
if(collisions(v)) return i;
}
}
ll a = 1;
while((double)((a+1)*(a+1) - 1) < (double)(e-s)/r) a++;
if(chk(s,a)) return dnc(s,s+a*a-1);
else return dnc(s+a*a, e);
}
int hack(){
int m = dnc(big/2,big);
int ans = m;
int f= 1;
while(f) {
f=0;
for (int i = 2; i * i <= m; i++) {
if (m % i) continue;
vector<ll> v;
v.pb(1), v.pb(m / i + 1);
if (collisions(v)) {
m /= i;
ans /= i;
f=1;
break;
}
}
}
return ans;
}
