#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[mxn], sufw[mxn], ans;

bool used[mxn];

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;
        mna[0] = 1;
        for(int i = 1 ; i <= n ; i++){
            cin >> a[i];
            used[i] = false;
            if(a[i] < a[mna[i - 1]])
                mna[i] = i;
            else
                mna[i] = mna[i - 1];
        }
        for(int i = 1 ; i <= m ; i++){
            cin >> wr[i].ri >> wr[i].wi;
        }
        sort(wr + 1, wr + 1 + m, cmp);
        sufw[m + 1] = 0;
        for(int i = m ; i >= 1 ; i--){
            sufw[i] = sufw[i + 1] + wr[i].wi;
        }
        que.push(make_pair(a[mna[wr[1].ri]] - sufw[1], 1));
        used[mna[wr[1].ri]] = true;
        for(int i = 2 ; i <= m ; i++){
            if(wr[i].ri == wr[i - 1].ri || mna[wr[i].ri] == mna[wr[i - 1].ri])
                continue;
            que.push(make_pair(a[mna[wr[i].ri]] - sufw[i], i));
            used[mna[wr[i].ri]] = true;
        }
        for(int i = 1 ; i <= n ; i++){
            if(!used[i]){
                fq.push(a[i]);
            }
        }
        ans = 0;
        di = m + 1;
        for(int pi, i = 1 ; i <= n ; i++){
            if(!que.empty()){
                while(que.top().second >= di){
                    pi = que.top().second;
                    fq.push(a[mna[wr[pi].ri]]);
                    que.pop();
                }
            }
            if(!que.empty() && !fq.empty()){
                if(que.top().first + sufw[di] < fq.top()){
                    ans += que.top().first + sufw[di];
                    di = que.top().second;
                    que.pop();
                }else{
                    ans += fq.top();
                    fq.pop();
                }
            }else{
                if(!que.empty()){
                    ans += que.top().first + sufw[di];
                    di = que.top().second;
                    que.pop();
                }else{
                    ans += fq.top();
                    fq.pop();
                }
            }
            cout << ans << " ";
        }
        cout << endl;
    }
    return 0;
}