#include "hack.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int hack() {
int l = (int)5e8, r = (int)1e9;
while (l < r) {
int mid = (l + r + 1) / 2;
int N = mid - l + 1;
int 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;
int t = l;
for (int i = 2; i * i <= l; 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;
}
