#include "hack.h"
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define sz(x) (int) x.size()
#define all(x) begin(x), end(x)
using namespace std;
#define pb push_back
using ll = long long;
using vi = vector<int>;
bool query(ll l, ll r) {
ll base = sqrt(r - l + 1);
vector<ll> v;
forsn(i, 1, base + 1) v.pb(i);
ll curr = base + l;
while (curr <= r) {
v.pb(curr);
curr += base;
}
v.pb(r + 1);
return collisions(v) != 0;
}
vector<ll> primes(ll n) {
vector<ll> p;
for (ll i = 2; i * i <= n; i++) {
if (n % i == 0) p.pb(i);
while (n % i == 0) n /= i;
}
if (n != 1) p.pb(n);
return p;
}
int hack() {
ll lo = 5e8, hi = 1e9;
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (query(lo + 1, mid)) hi = mid;
else lo = mid;
}
for (ll p : primes(hi)) {
while (hi % p == 0) {
if (collisions(vector<ll>{(hi / p), 2 * (hi / p)})) hi /= p;
else break;
}
}
return hi;
}
