#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> x, y, di, xf, xf1, xf2, xs, xs1, xs2;
mt19937 mt(time(NULL));
int l, r, m, fe, se;
const int s = 56000;
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;
}
while ((int)x.size() > 2) {
m = (int)x.size();
xf.clear();
xs.clear();
for (int i=0; i < m/2; ++i) xf.push_back(x[i]);
for (int i=m/2; i < m; ++i) xs.push_back(x[i]);
if (collisions(xf) != 0) {
x = xf;
continue;
}
if (collisions(xs) != 0) {
x = xs;
continue;
}
xf1.clear();
xf2.clear();
m = (int)xf.size();
for (int i=0; i < m/2; ++i) xf1.push_back(xf[i]);
for (int i=m/2; i < m; ++i) xf2.push_back(xf[i]);
xs1.clear();
xs2.clear();
m = (int)xs.size();
for (int i=0; i < m/2; ++i) xs1.push_back(xs[i]);
for (int i=m/2; i < m; ++i) xs2.push_back(xs[i]);
y.clear();
for (auto el : xf1) y.push_back(el);
for (auto el : xs1) y.push_back(el);
if (collisions(y) != 0) {
x = y;
continue;
}
y.clear();
for (auto el : xf2) y.push_back(el);
for (auto el : xs1) y.push_back(el);
if (collisions(y) != 0) {
x = y;
continue;
}
y.clear();
for (auto el : xf1) y.push_back(el);
for (auto el : xs2) y.push_back(el);
if (collisions(y) != 0) {
x = y;
continue;
}
y.clear();
for (auto el : xf2) y.push_back(el);
for (auto el : xs2) y.push_back(el);
x = y;
}
long long diff = x[1]-x[0];
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;
}
