#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010 * 4;
int mod = 998244353;
int n, m;
PII b[N];
PII d[N];
int a[N];
int lz[N];
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar('0' + x % 10);
}
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;
    d[p].first = 0;
    d[p].second = 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()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    build(1, n, 1);
    // cout << m << endl;
    for (int i = 1; i <= m; i++)
    {
        int r, w;
        r = read(), w = read();
        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++)
    {
        sum += a[i];
        write(sum);
        putchar(' ');
    }
    putchar('\n');
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}