#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include <set>
using namespace std;
int a[200008];
struct Node
{
    int r, w;
}p[200008];
bool cmp(Node aa, Node bb)
{
    return aa.r < bb.r;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n ; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m ; ++i)
    {
        cin >> p[i].r >> p[i].w;
    }
    sort(p+1,p+m+1,cmp);
    multiset<int> ms;
    int idx = 1;
    for (int i = 1; i <= m ; ++i)
    {
        int val;
        while( idx <= n && idx <= p[i].r )
        {
            ms.insert(a[idx]);
            idx++;
        }
        val = *ms.begin();
        ms.erase(ms.begin() );
        ms.insert(val-p[i].w);
    }
    while( idx <= n )
    {
        ms.insert(a[idx]);
        idx++;
    }
    int ans = 0;
    for (int i = 1; i <= n ; ++i)
    {
        ans += *ms.begin();
        ms.erase(ms.begin());
        cout << ans << " ";
    }
    cout << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }


    return 0;
}