#define ll long long
#define se second
#define fi first
using namespace std;
#include<utility>
#include<algorithm>
#include<vector>
#include<map>
#include<set>

const char nl = '\n';
const ll inf = 1e18;

vector <vector <int> > g;

    struct st{
        int x, i, u;
    };

    bool cmp(st a, st b) {
        if (a.x != b.x) {
            return a.x < b.x;
        } else {
            return a.u < b.u;
        }
    }

    std::vector<int> solve(
    std::vector<std::pair<int, int>> r,
    std::vector<ll> d,
    std::vector<int> s,
    std::vector<int> t,
    std::vector<bool> I
    ) {
        int n = r.size() + 1;
        int m = d.size();
        bool f = 1;
        g.resize(n);
        for (int i = 0; i < n - 1; i++) {
            if (!(r[i].fi == i && r[i].se == i + 1)) {
                f = 1;
            }
            g[r[i].fi].push_back(r[i].se);
            g[r[i].se].push_back(r[i].fi);
        }

        vector <int> ans;

        if (f) {
            map <ll, set <int> > h;
            map <ll, int> z;
            ans.assign(m, -1);
            vector <st> ev;
            for (int i = 0; i < m; i++) {
                ev.push_back({s[i], i, 0});
                ev.push_back({t[i], i, 1});
            }
            sort(ev.begin(), ev.end(), cmp);
            for (auto it : ev) {
                if (it.u == 0) {
                    if (z[d[it.i] - s[it.i]] || I[it.i]) {
                        ans[it.i] = it.x + 1;
                        if (I[it.i]) {
                            ans[it.i] = it.x;
                        }
                        z[d[it.i] - s[it.i]]++;
                        while (h[d[it.i] - s[it.i]].size() > 0) {
                            int j = *h[d[it.i] - s[it.i]].begin();
                            h[d[it.i] - s[it.i]].erase(j);
                            ans[j] = it.x;
                            z[d[it.i] - s[it.i]]++;
                        }
                    } else {
                        h[d[it.i] - s[it.i]].insert(it.i);
                    }
                } else {
                    h[d[it.i] - s[it.i]].erase(it.i);
                    if (ans[it.i] != -1) {
                        z[d[it.i] - s[it.i]]--;
                    }
                }
            }

            for (int i = 0; i < m; i++) {
                if (ans[i] == -1) {
                    ans[i] = 0;
                } else {
                    ans[i] = t[i] - ans[i] + 1;
                }
            }
            return ans;
        }
    };