#include <bits/stdc++.h>
#include "hack.h"
using namespace std;
using ll = long long;
const int nax = 1e9;
int n_used = nax;
const int skip = 35000;
// int QQ = 0;
mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
// ll collisions(vector<ll> v) {
// map<ll, ll> f;
// for(ll &i : v) f[i % n_used]++;
// ll q = 0;
// for(auto &i : f) {
// // cerr << i.first << " " << i.second << endl;
// q += i.second * (i.second - 1) / 2;
// }
// return q;
// }
bool better(vector<ll> A, vector<ll> B) {
vector<ll> tmp = A;
for(auto &i : B) tmp.push_back(i);
return collisions(tmp) != 0;
}
int hack() {
vector<ll> A, B; A.reserve(skip); B.reserve(nax / 4);
for(int i = 1; i <= skip; i++) {
A.push_back(i);
}
for(int i = (nax / 2 - ((nax / 2) % skip)); i <= nax + skip; i += skip) {
B.push_back(i);
}
while(A.size() > 1 || B.size() > 1) {
if(A.size() > B.size()) {
vector<ll> al, ar; al.reserve(A.size() / 2); ar.reserve(A.size() / 2);
for(int i = 0; i < A.size(); i++) {
if(i < A.size() / 2) al.push_back(A[i]);
else ar.push_back(A[i]);
}
if(better(ar, B))
A = ar;
else
A = al;
}
else {
vector<ll> bl, br; bl.reserve(B.size() / 2); br.reserve(B.size() / 2);
for(int i = 0; i < B.size(); i++) {
if(i < B.size() / 2) bl.push_back(B[i]);
else br.push_back(B[i]);
}
if(better(A, bl))
B = bl;
else
B = br;
}
}
ll a1 = A[0];
ll b1 = B[0];
int d = abs(a1 - b1);
auto get = [&](int d1) {
vector<int> fac;
int t = 2;
while(t * t <= d1) {
if(d1 % t == 0) {
fac.push_back(t);
d1 /= t;
}
else t++;
}
if(d1 > 1) fac.push_back(d1);
return fac;
};
for(auto &p : get(d)) {
d /= p;
if(collisions({1, d + 1}) == 0)
d *= p;
}
return d;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// n_used = 5;
// // cout << collisions({2, 15, 7, 27, 8, 30});
// // n_used = 358696241;
// for(int test = 1; test <= 10; test++) {
// assert(n_used == hack());
// cout << "OK\n";
// n_used = rng() % nax + 1;
// }
// return 0;
// }
