#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=1000005;
int a[N];
int s[N<<2],t[N<<2],mn[N<<2],b[N];
struct node{
    int r,w;
}c[N];
int cnt;
void pushup(int k){
    s[k]=min(s[k<<1],s[k<<1|1]);
    if(s[k<<1|1]<=s[k<<1])mn[k]=mn[k<<1|1];
    else mn[k]=mn[k<<1];
}
void build(int k,int l,int r){
    t[k]=0;
    if(l==r){
        s[k]=a[l];
        mn[k]=l;
        return ;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
    return ;
}
void pushdown(int k){
    if(t[k]){
        s[k<<1]+=t[k];
        s[k<<1|1]+=t[k];
        t[k<<1]+=t[k];
        t[k<<1|1]+=t[k];
        t[k]=0;
    }
}
void add(int k,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        s[k]+=v;
        t[k]+=v;
        return ;
    }
    pushdown(k);
    int mid=l+r>>1;
    if(R<=mid)add(k<<1,l,mid,L,R,v);
    else if(L>mid)add(k<<1|1,mid+1,r,L,R,v);
    else add(k<<1,l,mid,L,mid,v),add(k<<1|1,mid+1,r,mid+1,R,v);
    pushup(k);
}
int cmp(node x,node y){
    return x.r<y.r;
}
signed main(){
    int i,T;
    cin>>T;
    while(T--){
        scanf("%lld%lld",&n,&m);
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        build(1,1,n);cnt=0;
        for(i=1;i<=m;i++){
            int r,w;
            scanf("%lld%lld",&r,&w);
            add(1,1,n,1,r,-w);
            c[++cnt]=(node){r,w};
        }
        sort(c+1,c+cnt+1,cmp);
        int ans=0;
        for(i=1;i<=n;i++){
            ans+=s[1];
       //     cout<<mn[1]<<" "<<s[1]<<endl;
            add(1,1,n,mn[1],mn[1],1e15);
            while(c[cnt].r>=mn[1]&&cnt>0)add(1,1,n,1,c[cnt].r,c[cnt].w),cnt--;
            printf("%lld ",ans);
        }
        puts("");
    }
    return 0;
}
/*
2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
*/