#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
typedef pair<int,int> PII;
const int N=100010,M=1000010;
const int mod=998244353;
int INF = 1e9;
int h[N],e[M],ne[M],idx;
int T=1;





void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];


    priority_queue<int,vector<int>,greater<int> > q;

    map<int,int> mp;
    mp[n]=0;
    while(m--){
        int r,w;
        cin>>r>>w;

        r=min(r,n);

        mp[r]+=w;
    }

    int ls=1;
    for(auto [x,y]:mp){

        while(ls<=x){
            q.push(a[ls]);
            ls++;
        }

        int t=q.top();
        q.pop();
        t-=y;
        q.push(t);
    }

    LL res=0;

    for(int i=1;i<=n;i++){
        res+=q.top();
        q.pop();

        cout<<res<<" ";
    }

    cout<<endl;

}   
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //int T=1;
    cin>>T;
    while(T--) solve();
 
    return 0;
}