#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
int hack() {
ll l = 5e8, r = 1e9;
while (l < r) {
ll m = l+(r-l+1)/2;
int k = max(1LL,(ll)sqrtl(m-l+1));
vctr<ll> cur;
for (int i = 1; i <= k; ++i) {
cur.pb(i);
}
for (int i = l+k-1; i <= m; i += k) {
if (i > k)cur.pb(i);
}
if (cur.back() != m)cur.pb(m);
ll res = collisions(cur);
if (l == 2 && r == (ll)1e9)dbg(res);
if (res) {
r = m-1;
} else {
l = m;
}
}
vctr<int> v;
int x = l;
for (int i = 2; i*i <= x; ++i) {
if (x%i)continue;
v.pb(i);
while (x%i == 0)x /= i;
}
if (x > 1)v.pb(x);
int ans = l;
for (auto p : v) {
while (collisions({l,ans/p}) != 0) {
ans /= p;
}
}
return ans;
}
