#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
#define Genshin_Impact return
#define start 0
const int mod = 998244353;
const int N = 2e5 + 10;
int a[N];
struct node
{
    int rq, w;
    bool operator<(const node &W) const
    {
        if (W.rq == rq)
            return 1;
        return rq < W.rq;
    }
} p[N];
int nxt[N];
bool st[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        st[i] = 0;
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> p[i].rq >> p[i].w;
    }
    sort(p + 1, p + m + 1);
    int sum = 0, idx = m;
    int mi = 1e9 + 10, minn = -1;
    priority_queue<pii, vector<pii>, greater<pii>> q, q2;
    for (int i = n; i >= 1; i--)
    {
        while (idx >= 1 && p[idx].rq == i)
        {
            sum += p[idx].w;
            idx--;
        }
        nxt[i] = sum;
        q.push({a[i] - sum, i});
    }
    int now = n;
    vector<int> ans;
    int cnt = 0;
    int s = 0;
    int ls = n;
    for (int i = 1; i <= n; i++)
    {
        while (q.size() && q.top().second >= now)
        {
            q.pop();
        }

        int m1 = 1e15, m2 = 1e15;
        if (q.size())
        {
            m1 = min(m1, q.top().first + cnt);
        }
        if (q2.size())
        {
            m2 = min(m2, q2.top().first);
        }
        if (m1 < m2)
        {
            s += q.top().first + cnt;
            now = q.top().second;
            cnt = nxt[now];
            st[now] = 1;
            q.pop();
        }
        else
        {
            s += q2.top().first;
            q2.pop();
        }
        // cout << m1 << ' ' << m2 << ' ';
        // cout << now << ' ' << ls << '\n';
        for (int j = now; j <= ls; j++)
        {
            if (!st[j])
            {
                // cout << i << ": " << j << '\n';
                q2.push({a[j], j});
                st[j] = 1;
            }
        }
        ls = now;
        ans.push_back(s);
    }
    for (auto j : ans)
        cout << j << ' ';
    cout << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    Genshin_Impact start;
}