#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 10;

struct Node {
    int r, w;
    bool operator < (const Node &i) const {
        return r < i.r;
    }
} b[N];

int T, n, m, a[N];
ll s;
priority_queue<int, vector<int>, greater<int> > pq;

void Solve() {
    cin >> n >> m, s = 0;
    ll must = 1e18;
    for (int i = 1; i <= n; i++) cin >> a[i], must = min(must, (ll)a[i]);
    for (int i = 1; i <= m; i++) cin >> b[i].r >> b[i].w, s += b[i].w;
    sort(b + 1, b + m + 1);
    int id = 0;
    for (int i = 1, j = 1; i <= m; i++) {
        int mmin = 1e9, tmp = j;
        for (; j <= b[i].r; j++) if (mmin > a[j]) mmin = a[j], tmp = j;
        if (must > mmin - s) must = mmin - s, id = tmp;
        s -= b[i].w;
        if (n == 18 && m == 24 && i > 10 && b[i].r <= 9) cout << b[i].r << ' ' << b[i].w << '\n';
    }
    for (int i = 1; i <= n; i++) if (i != id) pq.push(a[i]);
    ll ans = 0;
    if (!id) pq.pop();
    for (int i = 1; i <= n; i++) {
        if (i != 1) ans += pq.top(), pq.pop();
        cout << ans + must << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--) Solve();
    return 0;
}