#include<bits/stdc++.h>
#include "infection.h"
using namespace std;
using ll=long long;

const ll N=1.5e5+55,inf=1e18;
bool bc[N];
ll ans[N],n,m;
vector<array<ll,2>>lef[N];
vector<ll>rig[N];

ll fw[4*N][2];

void upd(ll k,ll x,ll koi){
    k+=N+7;
    while(k<4*N){
        fw[k][koi]=min(fw[k][koi],x);
        k+=k&-k;
    }
}

ll qry(ll k,ll koi){
    k+=N+7;
    ll ret=inf;
    while(k){
        ret=min(ret,fw[k][koi]);
        k-=k&-k;
    }
    return ret;
}

void upd2(ll k,ll x,ll koi){
    k+=N+7;
    k=4*N-k;
    while(k<4*N){
        fw[k][koi]=max(fw[k][koi],x);
        k+=k&-k;
    }
}

ll qry2(ll k,ll koi){
    k+=N+7;
    k=4*N-k;
    ll ret=-inf;
    while(k){
        ret=max(ret,fw[k][koi]);
        k-=k&-k;
    }
    return ret;
}

std::vector<int> solve(
std::vector<std::pair<int, int>> R,
std::vector<long long> D,
std::vector<int> S,
std::vector<int> T,
std::vector<bool> I
){
    m=S.size();
    n=R.size()+1;

    for(int i=0;i<N;++i){
        rig[i].clear();
        lef[i].clear();
        bc[i]=0;
        ans[i]=0;
    }

    for(int i=0;i<m;++i){
        ++S[i];++T[i];
        bc[S[i]]|=I[i];
        ans[i]=0;
    }

    vector<int>ret;
    for(int i=0;i<m;++i){
        if(bc[S[i]])
            ans[i]=abs(S[i]-T[i])+1;
    }
    for(int i=0;i<m;++i){
        if(S[i]<=T[i]){//desno
            if(!bc[S[i]])lef[T[i]].push_back({S[i],i});
        }else
            if(I[i])rig[T[i]].push_back(S[i]); //obrati paznju na T[i]<S[i]
    }

    //reset za minimum;
    for(int i=0;i<4*N;++i){
        for(int j=0;j<2;++j)
            fw[i][j]=inf;
    }

    for(int i=1;i<=n;++i){
        for(ll rt:rig[i]){
            ll L=i,R=rt;
            upd(2*L-R,rt,rt&1);
        }
        for(auto[lf,gde]:lef[i]){
            ll rt=qry(lf,lf&1);
            if(rt>N)continue;
            ans[gde]=i-(rt+lf)/2+1;
        }
    }

    for(int i=1;i<=n;++i){
        lef[i].clear();
        rig[i].clear();
    }

    //riset za maximujm
    for(int i=0;i<4*N;++i){
        for(int j=0;j<2;++j)
            fw[i][j]=-inf;
    }

    for(int i=0;i<m;++i){
        if(S[i]>T[i]){
            if(!bc[S[i]])lef[T[i]].push_back({S[i],i});
        }else{
            if(I[i])rig[T[i]].push_back(S[i]);
        }
    }

    for(int i=n;i>=1;--i){
        for(ll lf:rig[i]){
            ll L=lf,R=i;
            upd2(2*R-L,lf,lf&1);
        }
        for(auto[rt,gde]:lef[i]){
            ll lf=qry2(rt,rt&1);
            if(lf<0)continue;
            //cout<<lf<<' '<<rt<<endl;
            ans[gde]=(lf+rt)/2-i+1;
        }
    }

    vector<int>RRRR;
    for(int i=0;i<m;++i)
        RRRR.push_back(ans[i]);
    return RRRR;
}
