# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
# include "infection.h"
//# include "grader.cpp"

template<class T> void chmin(T& A, const T& B) {A=min(A,B);}
template<class T> void chmax(T& A, const T& B) {A=max(A,B);}

const int INF=1e9;
const int MAX=1e6+11;

int n,m;
vector<int> adj[MAX];
int D[MAX];
int S[MAX];
int T[MAX];
bool I[MAX];
int inf[MAX];

pair<int,int> tree[MAX*4];
pair<int,int> lazy[MAX*4];

pair<int,int> operator + (pair<int,int> A, pair<int,int> B)
{
    pair<int,int> ans={min(A.first,B.first),max(A.second,B.second)};
    return ans;
}

void push_lazy(int v, int l, int r)
{
    tree[v]=tree[v]+lazy[v];
    if(l!=r)
    {
        lazy[v*2]=lazy[v*2]+lazy[v];
        lazy[v*2+1]=lazy[v*2+1]+lazy[v];
    }
    lazy[v]={INF,-INF};
}

void build(int v=1, int l=1, int r=n)
{
    tree[v]=lazy[v]={INF,-INF};
    if(l==r) return ;

    int mid=(l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

void add(int le, int ri, int d, int v=1, int l=1, int r=n)
{
    push_lazy(v,l,r);
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        chmin(lazy[v].first,d);
        chmax(lazy[v].second,d);
        push_lazy(v,l,r);
        return ;
    }

    int mid=(l+r)/2;
    add(le,ri,d,v*2,l,mid);
    add(le,ri,d,v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}

pair<int,int> query(int le, int ri, int v=1, int l=1, int r=n)
{
    push_lazy(v,l,r);
    if(ri<l or r<le) return {INF,-INF};
    if(l==r) return tree[v];

    int mid=(l+r)/2;
    return query(le,ri,v*2,l,mid)+query(le,ri,v*2+1,mid+1,r);
}

void calc(vector<int>& v)
{
    vector<int> L,R;
    for(int x: v)
    {
        if(S[x]<=T[x]) R.push_back(x);
        else L.push_back(x);
    }

    build();
    for(int i: R)
    {
        if(!I[i]) continue;
        int l=S[i],r=T[i];
        add(l,r,S[i]);
    }
    for(int i: L)
    {
        int l=T[i],r=S[i];
        int pos=query(l,r).second;
        if(pos<=r) inf[i]=(r-pos)/2;
    }

    build();
    for(int i: L)
    {
        if(!I[i]) continue;
        int l=T[i],r=S[i];
        add(l,r,S[i]);
    }
    for(int i: R)
    {
        int l=S[i],r=T[i];
        int pos=query(l,r).first;
        if(l<=pos) inf[i]=(pos-l)/2;
    }
}

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)
{
    n=R.size()+1,m=_D.size();
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        tie(u,v)=R[i];
        u++;v++;
        //adj[u].push_back(v);
        //adj[v].push_back(u);
    }
    for(int i=1;i<=m;i++)
    {
        D[i]=_D[i-1];
        S[i]=_S[i-1]+1;
        T[i]=_T[i-1]+1;
        I[i]=_I[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        inf[i]=INF;
    }

    vector<int> even,odd;
    for(int i=1;i<=m;i++)
    {
        if(S[i]%2==0) even.push_back(i);
        else odd.push_back(i);
    }

    calc(even);
    calc(odd);

    vector<int> ans;
    for(int i=1;i<=m;i++)
    {
        if(I[i]) ans.push_back(abs(S[i]-T[i])+1);
        else if(inf[i]==INF) ans.push_back(0);
        else ans.push_back(abs(S[i]-T[i])+1-inf[i]);
    }

    return ans;
}

/*
4 1
0 1
1 2
2 3
0 0 3 1
*/
