#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef double db;
#define int long long
const int N=2e6+5;
#define endl '\n'
vector<int>a;
struct node{
    int p,l,r;
    int la;
    int mi,pre;
}t[N];
void pushup(node&ans,node zer,node yer){
    ans.l=zer.l;
    ans.r=yer.r;
   ans.pre=zer.pre+yer.pre;
   ans.mi=min(zer.mi,yer.mi);
   ans.la=0;
    return;
}
void pushup(int p){
    pushup(t[p],t[p*2],t[p*2+1]);
}
void pushdown(int p){
    if(t[p].la){
        t[p*2].pre+=t[p].la;
        t[p*2+1].pre+=t[p].la;
        t[p*2].mi+=t[p].la;
        t[p*2+1].mi+=t[p].la;
        t[p*2].la+=t[p].la;
        t[p*2+1].la+=t[p].la;
        t[p].la=0;
        return;
    }
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
      t[p].la=0;
      t[p].mi=t[p].pre=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void change(int p,int l,int r,int x){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].la+=x;
        t[p].pre+=x;
        t[p].mi+=x;
        return;
    }
    pushdown(p);
    int mid=(t[p].r+t[p].l)/2;
    if(mid>=l)change(p*2,l,r,x);
    if(mid<r)change(p*2+1,l,r,x);
    pushup(p);
}
node ask(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p];
    }
    pushdown(p);
    int mid=(t[p].r+t[p].l)/2;
    if (r <= mid) {
        return ask(p*2,l,r);
    } else if (l > mid) {
        return  ask(p*2+1,l,r);
    } else {
        node res;
        pushup(res, ask(p*2,l,r), ask(p*2+1,l,r));
        return res;
    }
}
struct m1{
    int i,w;
    inline bool operator<(const m1&x){
        return i<x.i;
    }
};
int ask1(int p){
    if(t[p].l==t[p].r)return t[p].l;
    if(t[p*2].mi<=t[p*2+1].mi){
        return ask1(p*2);
    }else{
        return ask1(p*2+1);
    }
}
vector<m1>lx;
void solve(){
    int n,m;
    cin>>n>>m;
    a=vector<int>(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);

    lx=vector<m1>(m+5);
   // cout<<ask(1,2,2).pre<<endl;
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        lx[i].i=a,lx[i].w=b;
        change(1,1,a,-b);
    }
  //  cout<<ask(1,2,2).pre<<endl;
    sort(lx.begin()+1,lx.begin()+1+m);
    int ans=0;
    int l1=1,r1=m+1;
    for(int i=1;i<=n;i++){
       ans+=t[1].mi;
       cout<<ans<<" ";
       int p1=ask1(1);
       change(1,p1,p1,1e17);
       int l=1,r=r1;
       if(r1==0)continue;
       while(l<r){
           int mid=(l+r)/2;
           if(lx[mid].i>=p1)r=mid;
           else l=mid+1;
       }
       if(r==r1){
           if(lx[r].i>=p1){
               for (int j = l; j <= r1; j++) {
                   if (p1 - 1 >= 1) {
                       change(1, 1, p1 - 1, lx[j].w);
                   }
                   if (p1 + 1 <= lx[j].i) {
                       change(1, p1 + 1, lx[j].i, lx[j].w);
                   }
               }
               r1 = l - 1;
           }
       }else{
           for (int j = l; j <= r1; j++) {
               if (p1 - 1 >= 1) {
                   change(1, 1, p1 - 1, lx[j].w);
               }
               if (p1 + 1 <= lx[j].i) {
                   change(1, p1 + 1, lx[j].i, lx[j].w);
               }
           }
           r1 = l - 1;
       }
    }
    cout<<endl;
}

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