#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int mod = 998244353;
int n, m;
PII b[N];
int s[N];
PII d[N];
int a[N];
int lz[N];
void pushup(int p)
{
    d[p].first = min(d[2 * p].first, d[2 * p + 1].first);
    if (d[2 * p].first < d[2 * p + 1].first)
    {
        d[p].second = d[2 * p].second;
    }
    else
    {
        d[p].second = d[2 * p + 1].second;
    }
}
void updown(int p)
{
    if (lz[p])
    {
        d[p * 2].first += lz[p];
        d[p * 2 + 1].first += lz[p];
        lz[p * 2] += lz[p];
        lz[2 * p + 1] += lz[p];
        lz[p] = 0;
    }
}
void build(int s, int t, int p)
{
    lz[p] = 0;
    if (s == t)
    {
        d[p].first = a[s];
        d[p].second = s;
        return;
    }
    int mid = (s + t) / 2;
    build(s, mid, p * 2);
    build(mid + 1, t, 2 * p + 1);
    pushup(p);
}
void update(int l, int r, int c, int s, int t, int p)
{
    if (s >= l && t <= r)
    {
        d[p].first += c;
        lz[p] += c;
        return;
    }
    updown(p);
    int mid = (s + t) / 2;
    if (l <= mid)
    {
        update(l, r, c, s, mid, p * 2);
    }
    if (r > mid)
    {
        update(l, r, c, mid + 1, t, 2 * p + 1);
    }
    pushup(p);
}
PII getid(int l, int r, int s, int t, int p)
{
    if (l <= s && t <= r)
    {
        return d[p];
    }
    int mid = (s + t) / 2;
    updown(p);
    PII tt;
    tt.first = 1e18;
    if (l <= mid)
    {
        if (tt.first > getid(l, r, s, mid, p * 2).first)
        {
            tt = getid(l, r, s, mid, p * 2);
        }
    }
    if (r > mid)
    {
        if (tt.first > getid(l, r, mid + 1, t, 2 * p + 1).first)
        {
            tt = getid(l, r, mid + 1, t, 2 * p + 1);
        }
    }
    // cout << " " << tt.second << endl;
    return tt;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, n, 1);
    // cout << m << endl;
    for (int i = 1; i <= m; i++)
    {
        int r, w;
        cin >> r >> w;
        b[i].first = r;
        b[i].second = w;
        // cout << r << " " << w << endl;
    }
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= m; i++)
    {
        int r = b[i].first, w = b[i].second;
        update(1, r, -w, 1, n, 1);
        // PII t = getid(1, r, 1, n, 1);
        //  cout << t.second << endl;
        // a[t.second] -= w;
    }
    // sort(a + 1, a + 1 + n);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        PII t = getid(1, n, 1, n, 1);
        sum += t.first;
        update(t.second, t.second, 1e17, 1, n, 1);
        cout << sum << " ";
    }
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
/*
1
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*/