#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(4444);
const long long inf = 1e16;
uniform_int_distribution<long long>ran(1,inf);
const int constant = 30000;
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,c;
for(long long i : curr){
int x = rng()%3;
if(x==0){
a.push_back(i);
}
else if(x==1){
b.push_back(i);
}
else{
c.push_back(i);
}
}
if(a.size()==0||b.size()==0||c.size()==0)
continue;
if(a.size()>b.size()){
swap(a,b);
}
if(a.size()>c.size()){
swap(a,c);
}
vector<long long>ab = a;
ab.insert(ab.end(),b.begin(),b.end());
if(collisions(ab)){
curr=ab;
continue;
}
vector<long long>ac = a;
ac.insert(ac.end(),c.begin(),c.end());
if(collisions(ac)){
curr=ac;
continue;
}
vector<long long>bc = b;
bc.insert(bc.end(),c.begin(),c.end());
curr=bc;
}
///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;
}
