#include <bits/stdc++.h>
using namespace std;
typedef int uci;
#define int long long
#define F first
#define S second
#define ar array

void solve(){
    int N,M,K; cin >> N >> M;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > SA;
    vector<int> A(N); vector<pair<int,int>> RW(M);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        SA.push({A[i], i});
    }
    for(int i = 0; i < M; i++) {
        cin >> RW[i].F >> RW[i].S;
        RW[i].F--;
    }

    sort(RW.begin(), RW.end());



    multiset<int> be;

    vector<int> added(M);

    int mip = A[0];

    int earn = 0;
    int j = 0;

    for(int i = 0; i < N; i++) {
        mip = min(mip, A[i]);
        while(j < M && i >= RW[j].F) {earn += RW[j++].S; added[j-1] = earn - mip; be.insert(earn-mip);};
        
    }


    int jj = M-1;
    int earnd = 0;

    int mi = M;

    int tc = 0;

    for(int i = 0; i < N; i++) {
        int la = SA.top().first;
        mi = min(mi, SA.top().second);
        SA.pop();

        //for(auto x: be) cout << x << endl;

        while(jj >= 0 && mi <= RW[jj].F) { be.erase(be.find(added[jj])); earnd += RW[jj--].S; }

        //cout << "(" << la << " " << tc << " " << earnd<< " " << be.size() << ")" << endl;

        int score = la + tc - earnd;
        if(be.size()) score = min(score, tc - *be.rbegin());
        tc += la;

        cout << score;
        if(i == N-1) cout << '\n'; else cout << ' ';
    }

    //cout << "ok" << endl;
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    for(int i = 0; i < t; i++) 
        solve();
}