#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) 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';
}

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

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