#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

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], mmin[N], tmp[N], k[N];
ll s, sum[N];
priority_queue<pii, vector<pii>, greater<pii> > 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;
    b[m + 1].r = n;
    for (int i = 1, j = 1; i <= m + 1; i++) {
        mmin[i] = 1e9, tmp[i] = j;
        for (; j <= b[i].r; k[j] = i, j++) if (mmin[i] > a[j]) mmin[i] = a[j], tmp[i] = j;
        mmin[i] -= s, sum[i] = s;
        if (must > mmin[i]) must = mmin[i], id = tmp[i];
        s -= b[i].w;
    }
    for (int i = 1; i <= n; i++) if (i != id) pq.push({a[i], i});
    ll ans = 0;
    if (!id) pq.pop();
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            // i : b[k[id] - 1] ~ b[k[id]]
            pii x = pq.top(); pq.pop();
            ans += x.first;
            //cout << x.second << ' ' << b[k[id] - 1].r << '\n';
            if (x.second <= b[k[id] - 1].r) ans -= sum[k[id] - 1] - sum[k[x.second] - 1], id = x.second;
        }
        cout << ans + must << ' ';// << k[id] << '\n';
    }
    cout << '\n';
}

/*
1
18 24
561699155 345484852 420718917 108291879 553918474 392861085 299874093 28528146 248352314 398850144 248444258 89834833 251398697 101739017 240342391 320200928 481962939 343719433
5 354704
6 9355942
7 7098134
16 38746862
15 35848885
14 42058214
15 18411581
9 23207206
18 19518309
14 20707458
13 37204319
2 28394359
18 23182935
12 25058614
8 1748809
16 2149688
5 2353975
6 45758313
5 9382051
9 12223652
7 50871033
4 48795591
8 50421578
2 29796517
*/

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