#include "hack.h"
#include<bits/stdc++.h>
using namespace std;
// collisions
#define get collisions
#define ll long long
#define re exit (0);
#define pb push_back
const int p = 27512 , q = 18175 , M = 5e8 ;
vector<ll> merge ( vector <ll> Left , vector<ll> Right ) {
vector<ll> res ;
for ( auto x : Left ) res . push_back (x) ;
for ( auto x : Right ) res . push_back (x) ;
return res ;
}
mt19937 rng (time(0)) ;
int hack(){
vector<ll> A ;
for ( int i = 1 ; i <= p ; i ++ ) A . push_back (i) ;
for ( int i = 1 ; i <= q ; i ++ ) A . push_back (M+i*p) ;
shuffle(A.begin(),A.end(),rng) ;
int x ;
while ( A.size () > 2 )
{
vector <ll> left1 , left2 , right1, right2 ;
int N = A.size () ;
for ( int i = 0 ; i < N/4 ; i ++ ) left1 . pb (A[i]) ;
for ( int i = N/4 ; i < N/2 ; i ++ ) left2 . pb (A[i]) ;
for ( int i = N/2 ; i < N/2 + N/4 ; i ++ ) right1 . pb (A[i]) ;
for ( int i = N/2 + N/4 ; i < N ; i ++ ) right2 . pb (A[i]) ;
if ( get (merge(left1,left2))) A = merge (left1,left2) ;
else if ( get (merge(right1,right2))) A = merge (right1,right2) ;
else
{
if ( get (merge(left1,right1)) ) A = merge (left1,right1) ;
else if ( get (merge (left2,right1))) A = merge (left2,right1) ;
else if ( get (merge(left1,right2) )) A = merge (left1,right2) ;
else A = merge (left2,right2) ;
}
if ( A.size () == 2 )
{
x = abs (A[0]-A[1]) ; break ;
}
if ( A.size () == 3 )
{
if ( get ({A[0],A[1]})) x = abs (A[0]-A[1]) ;
else if ( get ({A[0],A[2]})) x = abs (A[0]-A[2]) ;
else x = abs (A[1]-A[2]) ;
break ;
}
}
int w = x ;
for ( int i = 2 ; i*i <= x ; i ++ )
{
if ( x % i == 0 )
{
while ( w % i == 0 )
{
w /= i ;
if ( get ({1,1+w}) == 0 )
{
w *= i ; break ;
}
}
}
}
return w ;
}
