#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll LNF = 1e18;

ll n, m, titi;
vector<ll> dep, ti, to;
vector<vector<ll>> up, g;
void dfs(ll v, ll par) {
    ti[v] = titi++;
    up[0][v] = par;
    for (ll i = 1; i < 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (auto &u : g[v]) {
        if (u == par) continue;
        dep[u] = dep[v] + 1;
        dfs(u, v);
    }
    to[v] = titi++;
}
bool is_p(ll v, ll u) {
    return (ti[v] <= ti[u] && to[v] >= to[u]);
}
ll lca(ll v, ll u) {
    if (is_p(v, u)) return v;
    if (is_p(u, v)) return u;
    for (ll i = 19; i >= 0; i--) {
        if (!is_p(up[i][v], u)) {
            v = up[i][v];
        }
    }
    return up[0][v];
}
ll dis(ll v, ll u) {
    return (dep[v] + dep[u] - 2 * dep[lca(v, u)] + 1);
}

struct Node {
    //coord, id_in_iz_arr
    ll c, id;
    ll iz, is_r;

    bool operator<(const Node &o) const {
        if (c != o.c) return c < o.c;
        if (is_r != o.is_r) return (is_r > o.is_r);
        return (id < o.id);
    }
};

//a.c < b.c
bool is_pair(const Node &a, const Node &b) {
    if (!a.is_r || b.is_r) return 0;
    if (a.iz && !b.iz) return 1;
    if (!a.iz && b.iz) return 1;
    return 0;
}
ll cost(const Node &a, const Node &b) {
    return abs(a.c - b.c);
}

struct Worker {
    //should heaten only so it wouldn't break any conds
    ll heat;
    set<pair<ll, Node>> cand;
    set<Node> sk;
    map<Node, ll> mem;

    void ins(Node z) {
        mem[z] = heat;
        if (z.is_r) {
            z.c -= mem[z];
        } else {
            z.c += mem[z];
        }
        sk.insert(z);
        auto it = sk.lower_bound(z);
        if (it != sk.begin() && next(it) != sk.end()) {
            if (is_pair(*prev(it), *next(it))) {
                cand.erase({cost(*prev(it), *next(it)), *prev(it)});
            }
        }
        if (it != sk.begin()) {
            if (is_pair(*prev(it), *it)) {
                cand.insert({cost(*prev(it), *it), *prev(it)});
            }
        }
        if (next(it) != sk.end()) {
            if (is_pair(*it, *next(it))) {
                cand.insert({cost(*it, *next(it)), *it});
            }
        }
    }
    void ers(Node z, bool from_main) {
        if (from_main) {
            if (z.is_r) {
                z.c -= mem[z];
            } else {
                z.c += mem[z];
            }
        }
        auto it = sk.lower_bound(z);
        if (it != sk.begin() && next(it) != sk.end()) {
            if (is_pair(*prev(it), *next(it))) {
                cand.insert({cost(*prev(it), *next(it)), *prev(it)});
            }
        }
        if (it != sk.begin()) {
            if (is_pair(*prev(it), *it)) {
                cand.erase({cost(*prev(it), *it), *prev(it)});
            }
        }
        if (next(it) != sk.end()) {
            if (is_pair(*it, *next(it))) {
                cand.erase({cost(*it, *next(it)), *it});
            }
        }
        sk.erase(z);
    }

    void heaten(ll x) {
        heat += x;
    }
    ll tim_to() {
        if (cand.empty()) return LNF;
        return (cand.begin()->first - 2 * heat);
    }
    ll make_op() {
        auto [__, ver] = *cand.begin();
        auto it = sk.lower_bound(ver);

        ll zo;
        if (!it->iz) {
            zo = it->id;
            ers(*it, 0);
        } else {
            zo = next(it)->id;
            ers(*next(it), 0);
        }
        return zo;
    }
    Worker() {
        heat = 0;
        cand = {};
        sk = {};
        mem = {};
    }
};
struct Manager {
    Worker w0, w1;

    void ins(Node w) {
        if (w.c % 2 == w1.heat % 2) {
            w1.ins(w);
        } else {
            w0.ins(w);
        }
    }
    void ers(Node w) {
        if (w1.mem.count(w)) {
            w1.ers(w, 1);
        } else {
            w0.ers(w, 1);
        }
    }
    void heaten(ll x) {
        w0.heaten(x);
        w1.heaten(x);
    }
    ll tim_to() {
        return min(w0.tim_to(), w1.tim_to());
    }
    ll make_op() {
        if (w0.tim_to() < w1.tim_to()) {
            return w0.make_op();
        }
        return w1.make_op();
    }

    Manager() {
        w0 = {};
        w1 = {};
    }
};

vector<int> solve(vector<pii> r, vector<ll> tim, vector<int> s, vector<int> t, vector<bool> is) {
    //так называемая аккуратная реализация сетиком
    n = r.size() + 1;
    m = is.size();

    vector<int> bec(m, -1);
    for (int i = 0; i < m; i++) {
        if (is[i]) {
            bec[i] = abs(s[i] - t[i]);
        }
    }

    ll g_tim = 0;
    //poka tim[i] = 0;
    Manager is_r = Manager();
    Manager is_l = Manager();
    vector<ll> us(m);
    deque<pii> ev;
    for (ll i = 0; i < m; i++) {
        ev.push_back({tim[i], i});
        ev.push_back({tim[i] + abs(s[i] - t[i]), i});
    }
    sort(ev.begin(), ev.end());

    auto ins = [&](ll id) {
        if (s[id] < t[id] == is[id]) {
            Node zz = Node();
            zz.c = s[id];
            zz.is_r = s[id] < t[id];
            zz.id = id;
            zz.iz = is[id];
            is_r.ins(zz);
        } else {
            Node zz = Node();
            zz.c = s[id];
            zz.is_r = s[id] < t[id];
            zz.id = id;
            zz.iz = is[id];
            is_l.ins(zz);
        }
    };
    auto ers = [&](ll id) {
        if (s[id] < t[id] == is[id]) {
            Node zz = Node();
            zz.c = s[id];
            zz.is_r = s[id] < t[id];
            zz.id = id;
            zz.iz = is[id];
            is_r.ers(zz);
        } else {
            Node zz = Node();
            zz.c = s[id];
            zz.is_r = s[id] < t[id];
            zz.id = id;
            zz.iz = is[id];
            is_l.ers(zz);
        }
    };

    while (true) {
        ll mn = (ev.empty() ? LNF : ev[0].first - g_tim);
        ll mn2 = min(is_r.tim_to(), is_l.tim_to());
        if (min(mn, mn2) == LNF) break;
        is_l.heaten(min(mn, mn2) - g_tim);
        is_r.heaten(min(mn, mn2) - g_tim);
        g_tim += min(mn, mn2);
        if (mn > mn2) {
            ll id;
            if (is_r.tim_to() < is_l.tim_to()) {
                id = is_r.make_op();
            } else {
                id = is_l.make_op();
            }
            bec[id] = abs(s[id] - t[id]) - (g_tim - tim[id]);
            if (s[id] < t[id]) {
                s[id] += (g_tim - tim[id]);
            } else {
                s[id] -= (g_tim - tim[id]);
            }
            is[id] = 1;
            ins(id);
        } else {
            ll id = ev[0].second;
            ev.pop_front();
            if (!us[id]) {
                us[id] = 1;
                ins(id);
            } else {
                ers(id);
            }
        }
    }

    for (auto &el : bec) el++;
    return bec;
}
