#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
const vector<int> PRIMES = {
27361, 27367, 27397, 27407, 27409, 27427,
27431, 27437, 27449, 27457, 27479, 27481,
27487, 27509, 27527, 27529, 27539, 27541
};
//const long long BB = 22993;
const long long MAXN = 1e9;
bool query(vector<long long> A, vector<long long> B){
for (auto u : B) A.push_back(u);
for (auto u : A){
//cout << u << " ";
}
//cout << '\n';
long long x = collisions(A);
return (x > 0);
}
int hack(){
static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(0, PRIMES.size() - 1);
const long long BB = PRIMES[dist(rng)];
vector<long long> A,B;
for (long long i = 1; i<=BB; i++){
A.push_back(i);
}
for (long long st = ((MAXN/2)/BB)*BB; st <= MAXN+(BB*10); st += BB){
B.push_back(st);
}
while (A.size() > 1 || B.size() > 1){
if (A.size() <= B.size()) swap(A,B); //ensures A is bigger
//split A
vector<long long> fst,scd;
for (long long i = 0; i<A.size(); i++){
if (i < A.size()/2) fst.push_back(A[i]);
else scd.push_back(A[i]);
}
if (query(fst, B)){
//it's inside here
A.clear();
for (auto u : fst) A.push_back(u);
}
else{
A.clear();
for (auto u : scd) A.push_back(u);
}
}
long long one = A[0];
long long two = B[0];
long long dif = abs(one-two);
vector<long long> fac;
long long diff = dif;
for (long long i = 2; i*i <= diff; i++){
while (diff % i == 0){
fac.push_back(i);
diff /= i;
}
}
if (diff > 1) fac.push_back(diff);
for (auto u : fac){
vector<long long> tst = {1, (dif/u)+1};
if (collisions(tst)){
dif /= u;
}
}
return dif;
}
