#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define pi pair<int,int>

const int N=2e5+10;
// const int INF=1e18;

int n,m;
int a[N],b[N];
int ls(int x) {return x<<1;};
int rs(int x) {return x<<1|1;};

struct quan{
    int r,w;
}q[N];

struct TreeNode{
    int l,r;
    int lazy;
    int pos;
    int minn=1e18;
}tree[N*4];

void pushup(int t){
    if(tree[ls(t)].minn<tree[rs(t)].minn){
        tree[t].minn=tree[ls(t)].minn;
        tree[t].pos=tree[ls(t)].pos;
    }
    else if(tree[ls(t)].minn>=tree[rs(t)].minn){
        tree[t].minn=tree[rs(t)].minn;
        tree[t].pos=tree[rs(t)].pos;
    }
}

void pushdown(int t){
    tree[ls(t)].lazy+=tree[t].lazy;
    tree[rs(t)].lazy+=tree[t].lazy;
    tree[ls(t)].minn+=tree[t].lazy;
    tree[rs(t)].minn+=tree[t].lazy;
    tree[t].lazy=0;
}

void build(int t,int l,int r){
    tree[t].l=l;
    tree[t].r=r;
    tree[t].minn=1e18;
    tree[t].lazy=0;
    if(l==r) {
        tree[t].pos=l;
        tree[t].minn=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(t),l,mid);
    build(rs(t),mid+1,r);
    pushup(t);
}

void modify(int t,int l,int r,int p){
    if(l<=tree[t].l&&tree[t].r<=r){
        tree[t].lazy+=p;
        tree[t].minn+=p;
        return;
    }
    pushdown(t);
    int mid=tree[t].l+tree[t].r>>1;
    if(l<=mid) modify(ls(t),l,r,p);
    if(r>mid) modify(rs(t),l,r,p);
    pushup(t);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=0;
    for(int i=1;i<=m;i++){
        cin>>q[i].r>>q[i].w;
        // cerr<<q[i].r<<" "<<q[i].w<<"\n";
        b[1]-=q[i].w;
        b[q[i].r+1]+=q[i].w;        
    }
    
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    for(int i=1;i<=n;i++){
        a[i]+=b[i];
        // cout<<a[i]<<" \n"[i==n];
    }
    build(1,1,n);
    sort(q+1,q+1+m,[](quan a,quan b){ return a.r<b.r;});
    int pp=m;
    int ans=0;
    vector<int> vt;
    for(int i=1;i<=n;i++){
        ans+=tree[1].minn;
        vt.push_back(ans);
        // cerr<<"pos= "<<tree[1].pos<<"\n";
        modify(1,tree[1].pos,tree[1].pos,1e18);
        // cerr<<i<<" "<<q[pp].r<<" "<<tree[1].pos<<"\n";
        while(pp&&q[pp].r>=tree[1].pos){
            // cerr<<"modify "<<i<<" "<<q[pp].r<<" "<<q[pp].w<<"\n";
            modify(1,1,q[pp].r,q[pp].w);
            pp--;
        }
    }
    for(auto t:vt){
        cout<<t<<" ";
    }
    cout<<"\n";
}

signed main(){
    IOS
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}