#include "infection.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
template<typename T1,typename T2>void chmn(T1 &x,const T2 &y){x=x<y?x:y;}
template<typename T1,typename T2>void chmx(T1 &x,const T2 &y){x=x>y?x:y;}
const int N=150050,lg=18;
vector<int>E[N];
int par[N][lg+1],depth[N];
void DFS(int u,int p=0){
    par[u][0]=p;
    depth[u]=depth[p]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])if(i!=p)DFS(i,u);
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
//vector<array<ll,3>>ev;
bool was[N],active[N];
vector<int>solve(vector<pair<int,int>>R,vector<long long>D,vector<int>S,vector<int>T,vector<bool>I1){
    int n=R.size()+1;
    for(auto &[u,v]:R)u++,v++;
    for(auto &i:S)i++;
    for(auto &i:T)i++;
    /*for(auto [u,v]:R){
        E[u].pb(v);
        E[v].pb(u);
    }
    DFS(1);*/
    int q=S.size();
    vector<int>res(q,0);
    auto solve=[&](){
        vector<array<int,3>>Qsl;
        vector<array<int,2>>evl;
        for(int i=0;i<q;i++){
            int u=S[i],v=T[i];active[i]=I1[i];
            if(u<=v){
                if(!active[i]){
                    Qsl.pb({u,v,i});
                }
            }
            else{
                swap(u,v);
                if(active[i]){
                    evl.pb({2*u-v,v});
                }
            }
            if(active[i])chmx(res[i],abs(u-v)+1);
        }
        sort(Qsl.begin(),Qsl.end());
        sort(evl.begin(),evl.end());
        set<int>st[2];
        for(int I=0,j=0;I<Qsl.size();I++){
            while(j<evl.size()&&evl[j][0]<=Qsl[I][0]){
                st[evl[j][1]%2].insert(evl[j][1]);
                j++;
            }
            auto [l,r,i]=Qsl[I];
            int bit=l%2;
            auto lb=st[bit].lower_bound(l);
            if(lb!=st[bit].end()){
                int x=(l+(*lb))/2;
                chmx(res[i],r-x+1);
            }
        }

        //edge case
        bool bul[n+5]={0};
        for(int i=0;i<q;i++){
            int u=S[i],v=T[i];
            if(u<=v&&active[i])bul[u]=true;
        }
        for(int i=0;i<q;i++){
            int u=S[i],v=T[i];
            if(u<=v&&bul[u])chmx(res[i],abs(u-v)+1);
        }
    };
    solve();
    for(int i=0;i<q;i++){
        S[i]=n+1-S[i];
        T[i]=n+1-T[i];
    }
    solve();
    return res;
}
