CF ROUND1026 C

// Problem: C. Racing
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)
// URL: https://codeforces.com/contest/2110/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

void solve_bili()
{
    ll n;
    cin >> n;
    vl ds(n);
    for (auto &x : ds)
        cin >> x;
    vector<a2l> rs(n);
    for (auto &x : rs)
        cin >> x[0] >> x[1];

    vector<a2l> opt(n);
    for (ll i = 0, l = 0, r = 0; i < n; ++i) {
        if (ds[i] != -1)
            l += ds[i], r += ds[i];
        else
            r += 1;
        l = max(l, rs[i][0]), r = min(r, rs[i][1]);
        if (l > r) {
            cout << -1 << '\n';
            return;
        }
        opt[i] = {l, r};
    }

    ll val = opt.back()[0];
    for (ll i = n - 1; i >= 0; --i) {
        if (ds[i] != -1)
            val -= ds[i];
        else {
            if (val >= (i > 0 ? opt[i - 1][0] : 0) && val <= (i > 0 ? opt[i - 1][1] : 0))
                ds[i] = 0;
            else
                ds[i] = 1;
            val -= ds[i];
        }
    }
    for (auto x : ds)
        cout << x << ' ';
    cout << '\n';
}

void solve_ac()
{
    ll n;
    cin >> n;
    vl ds(n);
    for (auto &x : ds)
        cin >> x;
    vector<a2l> rs(n);
    for (auto &x : rs)
        cin >> x[0] >> x[1];

    vl lmax(n + 1), rmin(n + 1, LLONG_MAX / 2);
    for (ll i = n; i > 0; --i) {
        lmax[i - 1] = max(lmax[i], rs[i - 1][0]);
        rmin[i - 1] = min(rmin[i], rs[i - 1][1]);
    }

    bool valid = true;
    for (ll i = 0, h = 0; valid && i < n; ++i) {
        if (ds[i] != -1)
            h += ds[i];
        else {
            ds[i] = 1;
            h += 1;
            if (rmin[i] == h)
                ds[i] = 0, h -= 1;
        }

        if (!(rs[i][0] <= h && h <= rs[i][1]))
            valid = false;
    }
    if (!valid) {
        cout << -1 << '\n';
        return;
    }
    for (auto x : ds)
        cout << x << ' ';
    cout << '\n';
}

void solve_edtorial()
{
    ll n;
    cin >> n;
    vl ds(n);
    for (auto &x : ds)
        cin >> x;
    vector<a2l> rs(n);
    for (auto &x : rs)
        cin >> x[0] >> x[1];

    vl pos;
    for (ll i = 0, h = 0; i < n; ++i) {
        if (ds[i] == -1) {
            pos.push_back(i);
        } else {
            h += ds[i];
        }

        if (h < rs[i][0]) {
            ll d = rs[i][0] - h;
            if (pos.size() < d) {
                cout << -1 << '\n';
                return;
            }
            while (d--) {
                ds[pos.back()] = 1;
                h += 1;
                pos.pop_back();
            }
        }
        if (h + pos.size() > rs[i][1]) {
            ll d = h + pos.size() - rs[i][1];
            if (d > pos.size()) {
                cout << -1 << '\n';
                return;
            }
            while (d--) {
                ds[pos.back()] = 0;
                pos.pop_back();
            }
        }
    }
    for (auto x : ds)
        cout << max(x, 0ll) << ' ';
    cout << '\n';
}

void solve2()
{
    ll n;
    cin >> n;
    vl ds(n);
    for (auto &x : ds)
        cin >> x;

    vector<a2l> rs;
    for (auto &x : rs)
        cin >> x[0] >> x[1];
    vl ans(n);

    ll hl = rs.back()[0], hh = rs.back()[1], delta = 0;
    for (ll i = n - 2; i >= 0; --i) {
        auto p = rs[i + 1], c = rs[i];
        if (ds[i] == 1) {
            delta += 1;
            hl -= 1;
            hh -= 1;
        } else {
        }
        if (hl > c[1] || hh < c[0]) {
            cout << -1 << '\n';
            return;
        }
    }

    for (auto x : ans)
        cout << x << ' ';
    cout << '\n';
}

void solve1()
{
    ll n;
    cin >> n;
    vl ds(n);
    for (auto &x : ds)
        cin >> x;

    vl ni;
    for (ll i = 0; i < n; ++i)
        if (ds[i] == -1)
            ni.push_back(i);
    reverse(ni.begin(), ni.end());

    vector<a2l> rs;
    for (auto &x : rs)
        cin >> x[0] >> x[1];
    vl ans(n);
    for (ll i = 0, hl = 0, hh = 0; i < n; ++i) {
        if (ds[i] != -1) {
            ans[i] = ds[i];
            hl += ds[i];
            hh += ds[i];
        } else {
            ll delta = rs[i][0] - hl;
            if (delta > 0) {
                auto it = lower_bound(ni.begin(), ni.end(), i, std::greater<ll>());
                if (ni.end() - it >= delta) {
                    for (ll j = 0; j < delta; ++j) {
                        ans[ni.back()] = 1;
                        ni.pop_back();
                    }
                    hh += delta;
                    hl += delta;
                } else {
                    cout << -1 << '\n';
                    return;
                }
            }
            if (hh < rs[i][0] || hl > rs[i][1]) {
                cout << -1 << '\n';
                return;
            }
        }
    }
    while (!ni.empty()) {
        ans[ni.back()] = 0;
        ni.pop_back();
    }
    for (auto x : ans)
        cout << x << ' ';
    cout << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t;
    cin >> t;
    while (t--)
        solve_bili();

    return 0;
};