#include <bits/stdc++.h>
#include "hack.h"
using namespace std;
const int MAXN = 1e9;
const int B = 27000;
vector<int> factorize(int x) {
assert(x > 1);
vector<int> primes;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
primes.push_back(i);
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
primes.push_back(x);
}
return primes;
}
int hack() {
int mn = (MAXN / 2) / B, mx = MAXN / B;
vector<int> big, small;
int cur = 1;
for (int i = mx; i > mn; i--) {
big.push_back(cur);
cur += B;
}
cur += mn * B;
assert((cur - big[0]) / B == mx);
for (int i = 1; i <= B; i++) {
small.push_back(cur + i);
}
auto good = [](const vector<int> &small, const vector<int> &big) {
vector<long long> v;
for (auto x : small) {
v.push_back(x);
}
for (auto x : big) {
v.push_back(x);
}
return collisions(v) > 0;
};
while (big.size() > 1 || small.size() > 1) {
if (big.size() > small.size()) {
int mid = big.size() / 2;
auto big_left = vector<int>(big.begin(), big.begin() + mid);
auto big_right = vector<int>(big.begin() + mid, big.end());
if (good(big_right, small)) {
big = big_right;
} else {
big = big_left;
}
} else {
int mid = small.size() / 2;
auto small_left = vector<int>(small.begin(), small.begin() + mid);
auto small_right = vector<int>(small.begin() + mid, small.end());
if (good(big, small_right)) {
small = small_right;
} else {
small = small_left;
}
}
}
int x = small[0] - big[0];
auto primes = factorize(x);
for (auto p : primes) {
while (x % p == 0) {
int nxt = x / p;
if (collisions({1, nxt + 1}) > 0) {
x = nxt;
} else {
break;
}
}
}
return x;
}
