#include "gap.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
void query(ll L, ll R, ll *mn, ll *mx) {
if(L > R) *mn = -1, *mx = -1;
else MinMax(L, R, mn, mx);
}
long long findGap(int T, int N) {
if(T == 1) {
ll ans = 1, L = 0, R = 1e18, l, r;
int cnt = N;
query(L, R, &L, &R);
while(cnt > 2) {
cnt -= 2;
query(L + 1, R - 1, &l, &r);
if(l == -1) {
ans = max(ans, R - L);
break;
}
ans = max({ans, l - L, R - r});
L = l, R = r;
}
return max(ans, R - L);
}
else {
ll L = 0, R = 1e18, l, r;
query(L, R, &L, &R);
ll cur = ceil(R - L + 1, N - 1);
vector<ll> v;
v.push_back(L), L++;
while(L < R) {
query(L, L + cur, &l, &r);
if(l != -1) {
v.push_back(l);
v.push_back(r);
}
L = L + cur + 1;
}
v.push_back(R);
ll ans = 1;
rep(i, 1, signed(v.size()) - 1)
ans = max(ans, v[i] - v[i - 1]);
return ans;
}
}
