#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ui = __int128;
ll findGap(int T, int N) {
if (T==1) {
vector<ll> v1;
ll x=0; ll y=1e18; ll a=-1; ll b=-1;
while (x <= y && v1.size()<N) {
MinMax(x,y,&a,&b);
if (a==-1) {
break;
}
if (a==b) {
v1.push_back(a); break;
} else {
v1.push_back(a);
v1.push_back(b);
}
x=a+1; y=b-1;
}
sort(v1.begin(),v1.end());
assert(v1.size()==N);
ll ans = 0;
for (ll i=0;i<(N-1);i++) {
ans = max(ans,v1[i+1]-v1[i]);
}
return ans;
} else {
vector<ll> v1;
ll x=0; ll y=1e18; ll a=-1; ll b=-1;
MinMax(x,y,&a,&b);
x=a;y=b;
v1.push_back(x); v1.push_back(y);
for (ll t=0;t<N;t++) {
ll ql = x + ((ui)t*(ui)(y-x-N+1))/(ui)N + t;
if (ql==x) {
ql++;
}
ll qr = x + ((ui)(t+1)*(ui)(y-x-N+1))/(ui)N + t;
if (qr==y) {
qr--;
}
if (ql>qr) {
continue;
}
MinMax(ql,qr,&a,&b);
if (a!=-1) {
v1.push_back(a);
v1.push_back(b);
}
}
sort(v1.begin(),v1.end());
ll ans = 0;
for (ll i=0;i<(v1.size()-1);i++) {
ans = max(ans,v1[i+1]-v1[i]);
}
return ans;
}
}
