#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> x;
vector<long long> y;
vector<long long> di;
mt19937 mt(time(NULL));
int l, r, m, fe, se;
const int s = 55000;
const long long tw = 1000000000000LL;
int hack(){
while (true) {
x.clear();
for (int i=0; i < s; ++i) x.push_back(mt()%tw+1LL);
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
if (collisions(x) != 0) break;
}
l = 0;
r = (int)x.size()-1;
fe = -1;
while (l <= r) {
m = (l+r)/2;
y.clear();
for (int i=0; i <= m; ++i) y.push_back(x[i]);
if (collisions(y) == 0) l = m+1;
else {
r = m-1;
fe = m;
}
}
for (int i=0; i < fe; ++i) {
if (collisions({x[i], x[fe]}) > 0) {
se = i;
break;
}
}
long long diff = x[fe]-x[se];
for (long long d=2LL; d*d <= diff; ++d) {
if (diff % d == 0LL) {
di.push_back(d);
di.push_back(diff/d);
}
}
di.push_back(diff);
sort(di.begin(), di.end());
int dsz = (int)di.size();
for (int p=0; p < dsz; ++p) {
vector<long long> v;
v.push_back(1LL);
v.push_back(di[p]+1LL);
if (collisions(v) == 1) return di[p];
}
return 0;
}
