#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
bool query (const vector<long long>& a, const vector<long long>& b) {
vector<long long> v;
v.reserve(a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
v.push_back(a[i]);
for (size_t i=0; i<b.size(); ++i)
v.push_back(b[i]);
return collisions(v);
}
void factor (long long x, vector<long long>& v) {
vector<long long> ret;
long long i=2;
while (i*i<=x){
if (!(x%i)){
v.push_back(i);
x/=i;
}
else
++i;
}
if (x>1)
v.push_back(x);
}
int hack(){
constexpr long long gap=31623;
vector<long long> a,b;
a.reserve(gap);
b.reserve(gap);
for (long long i=1; i<=gap; ++i)
a.push_back(i);
for (long long i=gap*(500000000/gap); i<=1000000000; i+=gap)
b.push_back(i);
while (a.size() || b.size()){
vector<long long> l,r;
if (a.size()>b.size()){
l.reserve(a.size()>>1);
r.reserve((a.size()>>1)+(a.size()&1));
for (size_t i=0; i<a.size()>>1; ++i)
l.push_back(a[i]);
for (size_t i=b.size()>>1; i<a.size(); ++i)
l.push_back(a[i]);
if (query(l,b))
a=l;
else
a=r;
}
else{
l.reserve(b.size()>>1);
r.reserve((b.size()>>1)+(b.size()&1));
for (size_t i=0; i<b.size()>>1; ++i)
l.push_back(b[i]);
for (size_t i=b.size()>>1; i<b.size(); ++i)
l.push_back(b[i]);
if (query(l,a))
b=l;
else
b=r;
}
}
long long d=b[0]-a[0];
vector<long long> factors;
factor(d,factors);
for (size_t i=0; i<factors.size(); ++i){
if (collisions({1,d/factors[i]+1}))
d/=factors[i];
}
return d;
}
