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

const ll N=1.5e5+55,inf=1e18;
ll bc[N],n,m;

ll ans[N];
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<m;++i){
        bc[S[i]]|=I[i];
        ans[i]=0;
    }

    //st[i][j][k]->segmentno od parnost od 0->levo, 1->desno
    //ako je na levo (0) drzim min
    //ako je na desno (1) drzim max

    vector<int>ret;
    for(int i=0;i<m;++i){
        if(bc[S[i]])
            ans[i]=abs(S[i]-T[i])+1;
    }
    //subtask 4 je samo dist izmedju likova u stablu
    //subtask 5: nacice se akko:
    //case 1: samo krecu iz istog, to je trivijalno
    //case 2: idu u suprotnim smerovima, ista im je parnos l i r, i seku se segmenti. tad se nalaze na (l+r)/2
    //stavim ih u klase po ono parnosti r i u koji smer idu
    //i onda ocu da nadjem u sustini iz neke klase segmenata, lika kojem mu je l (ili r) najblize mom, a da me sece
    //to mogu da uradim tako sto napravim segmentno preko ovih kurceva, i uzimam minimum r ono iz njega, 3v
    //moram da imam i za [l,r] da L<=(l+R)/2
    //odnosno da 2L<=l+R
    //odnosno 2L-R<=l
    //znaci treba mi i da je u rangeu, i da ima ovo
    //mogu da radim offline (sort po r ili nesto)
    //perzistentno?
    //ne, posto mi treba minimum
    //ako idem od nazad po l-ovima
    //onda mi samo treba L<=r,
    //i 2L-R<=l
    //znaci ako sam ja na [l,r], ja ocu neko [L,R] tako da je L<=r, i 2L-R<=l
    //ako idem po increasing L-ovima, dodajem ih u segmentno fenvikovo 2L-R+N, i odgovaram na likove sa tim r-om, da ovo radi


    //prvo resavam ja idem na desno, on ide na levo
    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;
        }
    }

    //sad ja idem levo, on ide desno
    //ja sam [l,r] on je [L,R]
    //ocu da mi je R>=l i R>=(L+r)/2, sto je 2R>=L+r, sto je 2R-L>=r

    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;
}
