#include "hack.h"
#include <vector>
using namespace std;
const int N = 1000000000;
typedef vector<long long> vl;
int hack() {
int lower = N / 2 + 1, upper = N + 1;
while (upper - lower > 1) {
int n = (lower + upper) / 2;
int m = 1;
while (m * m < n - lower)
m++;
int q = (n - lower + m - 1) / m;
vl aa(m + q);
for (int i = 0; i < m; i++)
aa[i] = i + 1;
for (int i = 0; i < q; i++)
aa[m + i] = min(m * (i + 1) + lower, n);
if (collisions(aa) == 0)
lower = n;
else
upper = n;
}
int n = lower, n_ = n;
for (int p = 2; p <= n_ / p; p++)
if (n_ % p == 0) {
while (n_ % p == 0)
n_ /= p;
while (n % p == 0 && collisions({ 1, n / p + 1 }) != 0)
n /= p;
}
if (n_ > 1)
if (n % n_ == 0 && collisions({ 1, n / n_ + 1 }) != 0)
n /= n_;
return n;
}
