#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
ll collisions(vector<ll> x);
ll calc(ll k, ll n) {
ll q=k/n;
ll r=k%n;
return r*(q*(q+1)/2)+(n-r)*(q*(q-1)/2);
}
int hack(){
int k= 100000;
vector<ll> x(k);
for(int i=0; i<k; i++){
x[i]=i+1;
}
ll val1 = collisions(x);
if(val1>0){
ll lo=2, hi=k, ans=k;
while(lo<=hi){
ll mid = lo+((hi-lo)>>1);
if(calc(k,mid) >= val1){
ans=mid;
lo=mid+1;
}
else hi=mid-1;
}
return (int)(ans);
}
ll b = 1000000000000LL;
for(int i=0; i<k; i++){
x[i]=(i+1)*b;
}
ll val2=collisions(x);
if(val2 > 0){
vector<ll> d;
for(ll i = 1; i*i <= b; i++){
if(b%i == 0){
d.pb(i);
if(i*i != b){
d.pb(b/i);
}
}
}
sort(d.begin(), d.end());
for(auto i : d){
if(i>1 && calc(k,i) == val2){
return (int)(i);
}
}
}
return k;
}
