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