#include <bits/stdc++.h>
#define int long long
// #define lson (rt << 1)
// #define rson (rt << 1 | 1)

using namespace std;

// template <class Info, class Tag>
// struct SegmentTree {
//     vector <Info> tr;
//     vector <Tag> tag;
//     int n;

//     SegmentTree (int N, vector <Info> a) {
//         n = N;
//         tr.resize (n * 4 + 10);
//         tag.resize (n * 4 + 10);
//         auto build = [&] (auto &&self, int rt, int l, int r) {
//             if (l == r) {
//                 tr[rt] = a[l];
//                 return;
//             }
//             int mid = (l + r) / 2;
//             self (self, lson, l, mid);
//             self (self, rson, mid + 1, r);
//             pushup (rt);
//         };
//         build (build, 1, 1, n);
//     }

//     void pushup (int rt) {
//         tr[rt] = tr[lson] + tr[rson];
//     }

//     void apply (int rt, const Tag &x) {
//         tr[rt].apply (x);
//         tag[rt].apply (x);
//     }

//     void pushdown (int rt) {
//         apply (lson, tag[rt]);
//         apply (rson, tag[rt]);
//         tag[rt] = Tag ();
//     }

//     void modify (int rt, int l, int r, int x, int y, const Tag &t) {
//         if (l > y || r < x) {
//             return;
//         }
//         if (l >= x && r <= y) {
//             apply (rt, t);
//             return;
//         }
//         pushdown (rt);
//         int mid = (l + r) / 2;
//         modify (lson, l, mid, x, y, t);
//         modify (rson, mid + 1, r, x, y, t);
//         pushup (rt);
//     }

//     Info query (int rt, int l, int r, int x, int y) {
//         if (l >= r && r <= y) {
//             return tr[rt];
//         }
//         pushdown (rt);
//         int mid = (l + r) / 2;
//         if (x <= mid && y > mid) {
//             return query (lson, l, mid, x, y) + query (rson, mid + 1, r, x, y);
//         } else if (x <= mid) {
//             return query (lson, l, mid, x, y);
//         } else {
//             return query (rson, mid + 1, r, x, y);
//         }
//     }
// };


// struct Tag {
//     int lazy = 0;

//     void apply (const Tag &x) & {
//         lazy += x.lazy;
//     }
// };

// struct Info {
//     int id;
//     int minn = inf;

//     void apply (const Tag &x) & {
//         minn += x.lazy;
//     }
// };

// Info operator+(const Info &x, const Info &y) {
//     if (x.minn < y.minn) {
//         return x;
//     } else {
//         return y;
//     }
// }

constexpr int inf = 1E18;

void solve () {
    int n, m;
    cin >> n >> m;

    vector <int> a (n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    vector <int> suf (n + 2);
    for (int i = 0; i < m; i ++) {
        int r, w;
        cin >> r >> w;
        suf[r] += w;
    }

    for (int i = n; i >= 1; i --) {
        suf[i] += suf[i + 1];
    }

    // vector <Info> info1 (n + 1);
    // for (int i = 1; i <= n; i ++) {
    //     info1[i].id = i;
    //     info1[i].minn = a[i] - suf[i];
    // }
    // vector <Info> info2 (n + 1);
    // for (int i = 1; i <= n; i ++) {
    //     info2[i].id = i;
    //     info2[i].minn = a[i];
    // }

    // SegmentTree <Info, Tag> seg1 (n, info1);
    // SegmentTree <Info, Tag> seg2 (n, info2);

    vector <int> p (n + 1);
    iota (p.begin (), p.end (), 0);
    sort (p.begin () + 1, p.end (), 
        [&](const int &x, const int &y) {
            return a[x] < a[y];
        }
    );

    set <pair <int, int>> set1;
    set <pair <int, int>> set2;

    int ans;
    int l = p[1];
    vector <int> b1 (n + 1), b2 (n + 1);
    for (int i = 1; i <= n; i ++) {
        b1[i] = a[i] - suf[i];
        ans = min (ans, b1[i]);
        if (i < l) {
            set1.insert ({b1[i], i});
        }
        b2[i] = a[i];
        if (i > l) {
            set2.insert ({b2[i], i});
        }
    }

    // auto [Minn, ID] = seg1.query (1, 1, n, 1, n);

    // seg1.modify (1, 1, n, l, l, {inf});
    // seg2.modify (1, 1, n, l, l, {inf});
    cout << ans << ' ';
    // cerr << 1 << '\n';

    int sum = a[l];
    for (int w = 2; w <= n; w ++) {
        ans = inf;
        if (l != 1) {
            // int k = seg1.query (1, 1, n, 1, l - 1).minn;
            int k = set1.begin ()->first;
            ans = min (ans, sum + k);
        }
        if (l != n) {
            // int k = seg2.query (1, 1, n, l + 1, n).minn;
            int k = set2.begin ()->first;
            ans = min (ans, sum + k - suf[l]);
        }
        // int ll=seg2.query (1, 1, n, 1, n).id;
        int ll = p[w];
        if (ll < l) {
            for (int i = ll; i < l; i ++) {
                set1.erase ({b1[i], i});
                if (i > ll) {
                    set2.insert ({b2[i], i});
                }
            }
            l = ll;
        } else {
            set2.erase ({b2[ll], ll});
        }
        // seg1.modify (1, 1, n, ll, ll, {inf});
        // seg2.modify (1, 1, n, ll, ll, {inf});
        // l=min(ll,l);
        sum += a[ll];
        cout << ans << ' ';
    }
    cout << '\n';
}

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    cin >> T;

    while (T --) {
        solve ();
    }

    return 0;
}