#include <bits/stdc++.h>
#include "hack.h"
using namespace std;
#define pb push_back
const int N = 1e9;
const int B = (int)sqrt(N);
int collision(vector<int> v){
sort(v.begin(), v.end());
for(int i=1;i<(int)v.size();i++)
if(v[i]==v[i-1]) return 1;
return 0;
}
vector<int> fac(int x){
vector<int> p;
for(int i=2;i*i<=x;i++){
if(x%i==0){
p.pb(i);
while(x%i==0) x/=i;
}
}
if(x>1) p.pb(x);
return p;
}
int hack(){
int mn=(N>>1)/B, mx=N/B;
vector<int>a,b;
a.reserve(mx-mn+5);
b.reserve(B+5);
for(int i=1,j=mx;j>mn;j--,i+=B) a.pb(i);
int c=a.back()+mn*B+B;
for(int i=1;i<=B;i++) b.pb(c+i);
auto g=[&](const vector<int>&x,const vector<int>&y){
vector<int> v;
v.reserve(x.size()+y.size());
for(int i:x) v.pb(i);
for(int i:y) v.pb(i);
return collision(v);
};
while(a.size()>1||b.size()>1){
if(a.size()>b.size()){
int m=a.size()/2;
vector<int>l(a.begin(),a.begin()+m),r(a.begin()+m,a.end());
a=g(b,r)?r:l;
}else{
int m=b.size()/2;
vector<int>l(b.begin(),b.begin()+m),r(b.begin()+m,b.end());
b=g(r,a)?r:l;
}
}
int x=b[0]-a[0];
for(int p:fac(x)){
while(x%p==0){
int y=x/p;
if(collision({1,y+1})) x=y;
else break;
}
}
return x;
}
