#include <bits/stdc++.h>
using namespace std;

#define qmx(a,b) a<b?b:a
#define qmn(a,b) a>b?b:a
#define ll long long
#define fr first
#define se second

const int mxn = 2e5+5;

priority_queue < pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int>> >que;

priority_queue < ll, vector<ll>, greater<ll> > fq;

struct token{
    int ri;
    ll wi;
}wr[mxn];

ll a[mxn], mna, ans;

inline bool cmp(struct token t1, struct token t2){
    return t1.ri < t2.ri;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test, di;
    cin>>test;
    while(test--){
        int n, m;
        cin >> n >> m;
        for(int i = 1 ; i <= n ; i++){
            cin >> a[i];
        }
        for(int i = 1 ; i <= m ; i++){
            cin >> wr[i].ri >> wr[i].wi;
        }
        sort(wr + 1, wr + 1 + m, cmp);
        mna = 1;
        for(int mi = 1, i = 1 ; i <= n ; i++){
            if(a[mna] > a[i])
                mna = i;
            while(mi <= m && wr[mi].ri >= mna){
                a[mna] -= wr[mi].wi;
                mi++;
            }
        }
        for(int i = 1 ; i <= n ; i++)
            fq.push(a[i]);
        ans = 0;
        for(int i = 1 ; i <= n ; i++){
            ans += fq.top();
            fq.pop();
            cout << ans << " ";
        }
        cout << endl;
    }
    return 0;
}