#include "gap.h"
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define ld long double
#define _1 first
#define _2 second
#define yes cout<<"Yes\n"
#define nah cout<<"No\n"
#define FFF ios_base::sync_with_stdio(0);cin.tie(0);
#define ipr pair<int,int>
#define ret return
#define intt int32_t
#define mid ((l+r)/2)
#define pb push_back
#define lll __int128
using namespace std;
int tst, ts;
intt mo = 0*(998244353)+(1e9+7)*1, dx[] = {0, -1, -1, 0}, dy[] = {1, 1, 2, 0};
int mul( int x, int y ) {
x%=mo;y%=mo;
ret (int) ( (long long) x * y % mo);
ret x*y;
}
int pwo( int x, long long y ) {
int res = 1;
for( int i = 63; i + 1; i-- )
res = mul( res, mul(res , ( ( 1ll << i )&y ? x : 1 )) );
ret res;
}
int dvii( int x, int y ) {
ret mul( x, pwo(y,mo-2) );
}
int oo( char x , char y) {
ret ( int )x - y;
}
int lgg( int x, int y ) {
int u = 0;
while( x ) {
u++;
x /= y;
}
ret u;
}//g++ -Wall -o "%e" "%f" && "./%e"
int mun( int x, int y ) {
while( x < y )x += mo;
ret ( x - y ) % mo;
}
int add( int x, int y ) {
ret x + y - ( mo * ( x + y >= mo ) );
ret x + y;
}
int lcm( int x, int y ) {
if(x*y==0)ret max(x,y);
int o=__gcd(x,y);
x/=o;
ret x*y;
}
//#define endl '\n';
#define nl no*2
#define nr no*2+1
const int M =5e4+7, N = 5e5+7, P = 1e12, inf = 1e18 ;
int n,m,k;
ipr ask(int x,int y){
int mn,mx;
MinMax(x,y,&mn,&mx);
ret{mn,mx};
}
long long findGap(intt T, intt N){
n=N;
int mx=1,o=0,in=inf;
if(T==1||n<=15){
ipr p{-1,inf+1};
vector<int>v;
while(v.size()<n){
p=ask(p._1+1,p._2-1);
v.pb(p._1);
v.pb(p._2);
}
sort(v.begin(),v.end());
for(int i=1;i<v.size();i++)
mx=max(mx,v[i]-v[i-1]);
ret mx;
}
else
for(int j=0;j<62;j++){
ipr p=ask(0,(1ll<<j));
if(p._1!=-1){
o=p._1;
break;
}
}
int u=0;
while(o+(1ll<<u)<=in){
//cout<<o<<endl;
for(int j=max(0ll,u-1);j<63;j++){
u=j;
ipr p=ask(o+1,min(o+(1ll<<j),in));
if(p._1!=-1){
mx=max(mx,p._1-o);
o=p._2;
break;
}
if((1ll<<j)+o>in)
break;
}
}
ret mx;
}
