#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(1234);
const long long inf = 1e14;
uniform_int_distribution<long long>ran(1,inf);
const int constant = 21000;
void roll(vector<long long> &arr){
unordered_set<long long>curr;
while(curr.size()<constant){
curr.insert(ran(rng));
}
arr.clear();
for(long long i : curr){
arr.push_back(i);
}
}
int hack(){
vector<long long>curr;
roll(curr);
while(collisions(curr)==0){
roll(curr);
}
while(curr.size()>2){
vector<long long>a,b;
for(long long i : curr){
if(rng()%2){
a.push_back(i);
}
else{
b.push_back(i);
}
}
if(a.size()==0||b.size()==0)
continue;
if(a.size()>1&&collisions(a)){
curr=a;
}
else if(b.size()>1&&collisions(b)){
curr=b;
}
else{
///reroll
continue;
}
}
///got distance
assert(curr.size()==2);
long long dist = abs(curr[1]-curr[0]);
///n is factor of dist
set<long long>facs;
for(int i = 2;1LL*i*i<=dist;i++){
if(dist%i==0){
facs.insert(i);
facs.insert(dist/i);
}
}
for(long long i : facs){
assert(i<=1e9);
if(collisions({1,1+i})){
return i;
}
}
assert(0);
return -1;
}
