#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int B = 31623;
const int inf = 1e9;
int ans;
ll collisions(vector<ll> v) ;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll n){
ll x = rng();
return abs(x) % n + 1;
}
void expiriment(int x){
vector<ll> v;
v.push_back(1);
v.push_back(1 + x);
if((collisions(v) == 1)) ans = min(ans , x);
}
ll query(vector<int> a , vector<int> b){
set<int> st;
for(auto to : a) st.insert(to);
for(auto to : b) st.insert(to);
vector<ll> q;
for(auto to : st) q.push_back(to);
return collisions(q);
}
int hack(){
vector<int> a , b;
for(int i = 1;i <= B; ++ i) a.push_back(i);
for(int i = B * 2; i <= inf + B; i += B) b.push_back(i);
while(a.size() > 1 or b.size() > 1){
//cout << a.size() << ' ' << b.size() << '\n';
int sa = a.size() , sb = b.size();
int ma = sa / 2 , mb = sb / 2;
if(a.size() > b.size()){
vector<int> c;
for(int i = 0;i < ma; ++ i) c.push_back(a[i]);
if(query(c , b)) a = c;
else{
reverse(a.begin() , a.end());
while(ma --) a.pop_back();
}
}
else{
vector<int> c;
for(int i = 0;i < mb; ++ i) c.push_back(b[i]);
if(query(c , a)) b = c;
else{
reverse(b.begin() , b.end());
while(mb --) b.pop_back();
}
}
}
ll d = abs(a.front() - b.front());
ans = inf;
//cout << d << ' ';
for(ll i = 1;i * i <= d; ++ i){
if(d % i == 0){
//cout << i << ' ';
expiriment(i);
if(d / i != i and d / i <= 1e9) expiriment(d / i);
}
}
return ans;
}
