#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);
}
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(al, B))
A = al;
else
A = ar;
}
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(bl, A))
B = bl;
else
B = br;
}
}
ll a1 = A[0];
ll b1 = B[0];
int d = abs(a1 - b1);
int d2 = d;
vector<int> primes;
for(int i = 2; i * i <= d; i++) {
if(d % i == 0) {
primes.push_back(i);
d /= i;
}
}
if(d > 1) primes.push_back(d);
for(auto &p : primes) {
d2 /= p;
if(collisions({1, d2 + 1}) == 0)
d2 *= p;
}
return d2;
}
// 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++) {
// cout << n_used << "\n";
// cout << hack() << "\n\n\n";
// n_used = rng() % nax + 1;
// }
// return 0;
// }
