#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];
bool f[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});
    for (int i = 1; i <= n; i++) pq.push({a[i], i});
    ll ans = 1e18, summ = 0;
    //f (!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';*/
        ans = 1e18;
        for (int j = 1; j <= m + 1; j++) {
            // tmp[j]
            if (f[tmp[j]]) ans = min(ans, summ + pq.top().first - a[tmp[j]] + mmin[j]);
            else ans = min(ans, summ + mmin[j]);
        }
        summ += pq.top().first, f[pq.top().second] = 1, pq.pop();
        cout << ans << ' ';
    }
    cout << '\n';
    while (!pq.empty()) pq.pop();
    fill(f + 1, f + n + 1, 0);
}

/*
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;
}