#include<bits/stdc++.h>
using namespace std;
const int N=1919810;

typedef long long ll;
typedef pair<ll,ll> PII;
int n,m;
ll val[N];
ll a[N];
ll mn[N],mnt[N];
ll ans[N];

void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n+1;i++) val[i]=0;
    for(int i=1;i<=m;i++){
        int r,w;
        scanf("%d%d",&r,&w);
        val[r]-=w;
    }
    for(int i=n;i>0;i--) val[i]+=val[i+1];
    
    mn[0]=1e18;
    mnt[0]=1e18;
    for(int i=1;i<=n;i++) val[i]+=a[i];
    // for(int i=1;i<=n;i++) cout<<val[i]<<" ";
    // cout<<endl;
    for(int i=1;i<=n;i++){
        if(val[i]<mn[i-1]){
            mn[i]=val[i];
            mnt[i]=i;
        }else{
            mn[i]=mn[i-1];
            mnt[i]=mnt[i-1];
        }
    }
    vector<int> vv;
    for(int i=n;i>=1;i--){
        while(vv.size()&&val[vv.back()]>val[i]) vv.pop_back();
        vv.push_back(i);
    }
    reverse(vv.begin(),vv.end());
    int j=vv.size()-1;
    // cout<<j<<endl;
    multiset<PII> se;
    for(int i=vv[j]+1;i<=n;i++) se.insert({a[i],i});
    ll tot=val[vv[j]];
    ans[1]=tot;
    for(int i=2;i<=n;i++){
        if(se.size()==0||(j!=0&&(*se.begin()).first>=val[vv[j-1]]-val[vv[j]]+a[vv[j]])){
            for(int k=vv[j]-1;k>vv[j-1];k--) se.insert({a[i],i});
            tot+=val[vv[j-1]]-val[vv[j]]+a[vv[j]];
            j--;
        }else{
            tot+=(*se.begin()).first;
            se.erase(se.begin());
        }
        ans[i]=tot;
    }
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    printf("\n");
}

int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
}