#include "hack.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int hack() {
ll l = (ll)5e8, r = (ll)1e9;
while (l < r) {
ll mid = (l + r + 1) / 2;
ll N = mid - l + 1;
ll x = (int)sqrt(N);
set<ll> A;
for (int i = 1; i <= x; i++) A.emplace(i);
for (int i = l; i <= mid; i += x) A.emplace(i);
A.emplace(mid);
vector<ll> Q;
for (auto &e : A) Q.emplace_back(e);
if (collisions(Q)) r = mid - 1;
else l = mid;
}
vector<ll> p;
ll t = l;
for (int i = 2; i * i <= t; i++) {
while (t % i == 0) p.emplace_back(i), t /= i;
}
if (t > 1) p.emplace_back(t);
for (auto &e : p) {
vector<ll> Q = {1, l / e + 1};
if (collisions(Q)) l /= e;
}
return l;
}
