#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+1;
int a[N];
struct Node{
    int r;
    int x;
}node[N];
bool cmp(Node a,Node b){
    return a.r<b.r;
}
int pre[N];
int ans[N];
int flag[N];
int n,m;
void solve(){
    cin>>n>>m;
    int suma=0;
    priority_queue<pair<int,int>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>=2){
            q.push({a[i],i});
        }
        suma+=a[i];
        flag[i]=0;
    }
    int sum=0;
    for(int i=1;i<=m;i++){
        cin>>node[i].r>>node[i].x;
        sum+=node[i].x;
    }
    sort(node+1,node+1+m,cmp);
    int l=1;
    for(int i=1;i<=n;i++){
        while(i>node[l].r&&l<=m){
            sum-=node[l].x;
            l++;
        }
        pre[i]=sum;
    }
    int nxt=2;
    int fir=1;
    ans[n]=suma-pre[1];
    for(int i=n-1;i>=2;i--){
        int tmp=ans[i+1];
        int tmpa=tmp+pre[fir]-a[fir]-pre[nxt];
        while(q.size()>0&&flag[q.top().second]){
            q.pop();
        }
        int tmpb=1e18;
        if(q.size()>0){
            tmpb=tmp-q.top().first;     
        }
        ans[i]=min(tmpa,tmpb);
        if(tmpa<tmpb){
            flag[fir]=1;
            fir=nxt;
            flag[fir]=1;
            for(int j=nxt+1;j<=n;j++){
                if(flag[j]==0){
                    nxt=j;
                    break;
                }
                nxt=n+1;
            }
        }
        else{
            flag[q.top().second]=1;
            if(flag[nxt]==1){
                for(int i=nxt+1;i<=n;i++){
                    if(flag[i]==0){
                        nxt=i;
                        break;
                    }
                    nxt=n+1;
                }

            }
            q.pop();
        }
    }
    ans[1]=a[fir]-pre[fir];
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __;
    cin>>__;
    while(__--){
        solve();
    }
}