#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#include"gap.h"
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
long long findGap(int T, int N){
int n=N;
vc<ll>l(n+1),r(n+1);
ll*a;
ll*b;
MinMax(0,2e18,a,b);
l[0]=*a,r[0]=*b;
ll W=r[0]-l[0];
ll per=(W+n-1)/n;
for(int i=0;i<n;i++){
ll*a;
ll*b;
MinMax(per*i+l[0],per*(i+1)+l[0],a,b);
l[i+1]=*a,r[i+1]=*b;
}
vc<ll>vs;
rep(i,n){
if(l[i+1]!=-1)vs.push_back(l[i+1]);
if(r[i+1]!=-1)vs.push_back(r[i+1]);
}
vs.push_back(l[0]);
vs.push_back(r[0]);
sort(all(vs));
ll ans=0;
rep(i,vs.size()-1){
chmax(ans,vs[i+1]-vs[i]);
}
return ans;
}
