#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 rem = m;
for (int i = 2; i * i <= m; i++) {
if (rem % i) continue;
vector<ll> v;
v.pb(1), v.pb(ans / i + 1);
while (collisions(v)) {
ans /= i;
if(ans % i) break;
v.clear();
v.pb(1), v.pb(ans / i + 1);
}
while(rem % i == 0) rem /= i;
}
if(rem != 1) {
vector<ll> v;
v.pb(1), v.pb(ans / rem + 1);
while (collisions(v)) {
ans /= rem;
if (ans % rem) break;
v.clear();
v.pb(1), v.pb(ans / rem + 1);
}
}
return ans;
}
