#include"hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9+1;
int ans(int l, int r){
if(l == r) return l;
int ln = r-l+1;
if(ln <= 10){
if(collisions({1,l})) return ans(l,l);
return ans(l+1, r);
}
int k = (int)sqrt(ceil(ln/2.f));
vector<int> val(2*k);
iota(val.begin(), val.end(), 1);
for(int i = 0; i < k; i++) val[i+k] = max(l-1, k)+i*k+1;
if(collisions(val)) return ans(l, val[2*k-1]);
return ans(val[2*k-1]+1, r);
}
signed hack(){
return ans(2, inf)-1;
}
