#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
struct prq{
    priority_queue<pll,vpl,greater<pll>> cur, er;
    prq(){}
    void push(pll o){cur.push(o);}
    void erase(pll o){er.push(o);}
    void clean(){
        while(!cur.empty() && !er.empty() && cur.top()==er.top()){
            cur.pop();er.pop();
        }
    }
    pll top(){
        clean();
        return cur.top();
    }
};

struct seg{
    vll bl, vl;
    ll n;
    vector<prq> bs;
    seg(){}
    seg(ll m):n(1<<(32-__builtin_clz(m-1))){
        bl = vll(n*2);
        vl = vll(n, 1e16);
        bs = vector<prq>(n);
        for(ll i = n; i < n*2; ++i){bl[i]=i-n;bs[i-n].push({1e16,-1});}
        for(ll i = n-1; i > 0; --i)bl[i]=bl[i*2];
    }
    ll cmp(ll a, ll b){
        if(vl[a]>vl[b])return b;
        return a;
    }
    void upd(ll i, ll v, ll j){
        bs[i].push({v,j});
        vl[i] = bs[i].top().f;
        i+=n;
        for(i/=2; i>0; i/=2){
            bl[i] = cmp(bl[i*2],bl[i*2+1]);
        }
    }
    void rem(ll i, ll v, ll j){
        bs[i].erase({v,j});
        vl[i] = bs[i].top().f;
        i+=n;
        for(i/=2; i>0; i/=2){
            bl[i] = cmp(bl[i*2],bl[i*2+1]);
        }
    }
    pll que(ll a, ll b){
        ll ans = a;
        for(a+=n,b+=n;a<=b;a/=2,b/=2){
            if(a%2==1)ans = cmp(ans, bl[a++]);
            if(b%2==0)ans = cmp(ans, bl[b--]);
        }
        return bs[ans].top();
    }
};



vector<int> solve(vector<pair<int, int>> r,vll d,vi s,vi t,vector<bool> inf){
    ll n = r.size()+1,m=d.size();
    vi ans(m);
    vvl ri(n), le(n), rm(n);
    for(ll i = 0; i < m; ++i){
        if(inf[i]){
            ans[i] = abs(t[i]-s[i])+1;
        }
        if(t[i]>=s[i])ri[s[i]].pb(i);
        else{
            if(ans[i]==0)le[s[i]].pb(i);
            if(2*t[i]-s[i]>=0)rm[2*t[i]-s[i]].pb(i);
        }
    }
    seg S1(n),S0(n);
    set<pll> helt0;
    set<pll> helt1;
    for(ll j = n-1; j >= 0; --j){
        for(ll i:le[j]){
            if(s[i]%2==0)helt0.insert({s[i],i});
            if(s[i]%2==1)helt1.insert({s[i],i});
        }
        for(ll i:ri[j]){
            if(ans[i]==0 && s[i]%2==0){
                ll o = S0.que(s[i],n-1).f;
                o = (o+s[i])/2;
                if(o<=t[i]){
                    ans[i]=t[i]-o+1;
                }
            }
            else if(ans[i]==0 && s[i]%2==1){
                ll o = S1.que(s[i],n-1).f;
                o = (o+s[i])/2;
                if(o<=t[i]){
                    ans[i]=t[i]-o+1;
                }
            }
            if(ans[i]>0 && s[i]%2==0){
                ll x = t[i]-ans[i]+1;
                while(!helt0.empty()){
                    auto it = helt0.lower_bound(make_pair(2*x-s[i],0));
                    if(it==helt0.end())break;
                    auto [y, k] = *it;
                    ll z = (s[i]+y)/2;
                    if(z>t[i])break;
                    else if(z>=t[k]){
                        ans[k] = z-t[k]+1;
                        S0.upd(s[k], s[k], k);
                    }
                    helt0.erase(it);
                }
            }
            else if(ans[i]>0 && s[i]%2==1){
                ll x = t[i]-ans[i]+1;
                while(!helt1.empty()){
                    auto it = helt1.lower_bound(make_pair(x,0));
                    if(it==helt1.end())break;
                    auto [y, k] = *it;
                    ll z = (x+y)/2;
                    if(z>t[i])break;
                    else if(z>=t[k]){
                        ans[k] = z-t[k]+1;
                        S1.upd(s[k], s[k], k);
                    }
                    helt1.erase(it);
                }
            }
        }
        for(ll i:rm[j]){
            if(ans[i]==0)continue;
            if(s[i]%2==0){
                S0.rem(s[i],s[i],i);
            }
            else{
                S1.rem(s[i],s[i],i);
            }
        }
    }

    return ans;
}