#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];
bool f[N];
ll s, sum[N];
priority_queue<ll, vector<ll>, greater<ll> > pq;

void Solve() {
    cin >> n >> m, s = 0;
    for (int i = 1; i <= n; i++) cin >> 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 mmin = 1e9, tmp = 0;
    for (int i = 1, j = 1; i <= m; i++) {
        for (; j <= b[i].r; j++) if (mmin > a[j]) mmin = a[j], tmp = j;
        a[tmp] -= b[i].w, mmin = a[tmp], s -= b[i].w;
    }
    for (int i = 1; i <= n; i++) pq.push(a[i]);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += pq.top(), pq.pop();
        cout << ans << ' ';
    }
    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

2
10 14
17 37 59 65 53 73 68 177 160 111
10 177
5 193
2 30
3 63
2 339
3 263
5 178
2 190
9 23
10 328
10 200
9 8
3 391
6 230
12 9
152 306 86 88 324 59 18 14 42 260 304 55
3 50
2 170
1 252
7 811
1 713
7 215
10 201
4 926
8 319
*/

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