#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ll long long
#define int128 __int128
#define ull unsigned long long
#define endl "\n"
#define pi acos(-1)
#define pii pair<int, int>
const double eps = 1e-6;
const int N = 1e6 + 10, M = 1010, INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[N];
struct node
{
    int r, w;
} s[N];
bool cmd(node x, node y)
{
    return x.r < y.r;
}
int pr[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i <= m; i++)
        pr[i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int r, w;
        cin >> r >> w;
        s[i] = {r, w};
    }
    sort(s + 1, s + m + 1, cmd);
    for (int i = 1; i <= m; i++)
        pr[i] = pr[i - 1] + s[i].w;
    int mi = 1e18;
    int u = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = m;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (s[mid].r >= i)
                r = mid - 1;
            else
                l = mid;
        }
        // cout << i << ' ' << l << endl;
        int res = a[i] - (pr[m] - pr[l]);
        if (res < mi)
        {
            mi = res;
            u = i;
        }
        else if (mi == res)
        {
            if (a[u] < a[i])
                u = i;
        }
    }
    vector<int> v;
    for (int i = 1; i <= n; i++)
    {
        if (i != u)
            v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    cout << mi << ' ';
    for (auto i : v)
    {
        mi += i;
        cout << mi << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios;
    int T = 1;
    cin >> T;
    // cout << fixed << setprecision(8);
    for (int i = 1; i <= T; i++)
    {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}