#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
const int N = 1e9;
const int N2 = 5e8;
const int k = 35000;
const int b2 = N2 / k;
const int b = N / k;
int hack(){
vector<vector<int>> s(2);
for(int i = 1; i <= k; i++) s[0].pb(i + 1);
for(int i = b2; i <= b + 1; i++) s[1].pb(i * k);
function<int(vector<int>&, vector<int>&)> query = [&](vector<int>& s1, vector<int>& s2){
vector<ll> cur;
for(int i : s1) cur.pb(i);
for(int i : s2) cur.pb(i);
ll ret = collisions(cur);
return ret > 0;
};
while(s[0].size() > 1 || s[1].size() > 1){
if(s[0].size() > s[1].size()){
vector<int> sl, sr;
for(int i = 0; i < (int) s[0].size() / 2; i++){
sl.pb(s[0][i]);
}
for(int i = (int) s[0].size() / 2; i < (int) s[0].size(); i++){
sr.pb(s[0][i]);
}
if(query(sr, s[1])){
s[0] = sr;
}
else{
s[0] = sl;
}
}
else{
vector<int> sl, sr;
for(int i = 0; i < (int) s[1].size() / 2; i++){
sl.pb(s[1][i]);
}
for(int i = (int) s[1].size() / 2; i < (int) s[1].size(); i++){
sr.pb(s[1][i]);
}
if(query(sl, s[0])){
s[1] = sl;
}
else{
s[1] = sr;
}
}
}
int ans = s[1][0] - s[0][0];
int res = ans;
for(int i = 2; i * i <= ans; i++){
while(ans % i == 0){
if(collisions({1ll, res / i + 1})){
ans /= i;
res /= i;
}
else
break;
}
while(ans % i == 0){
ans /= i;
}
}
if(ans > 1 && collisions({1ll, (ll) res / ans + 1}))
res /= ans;
return res;
}
