#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int MAXN=2e5+5;
struct SegmentTree{
    int l,r,minn;
    int lazy;
}tr[MAXN];
int a[MAXN];
void update(int rt)
{
    tr[rt].minn=min(tr[ls].minn,tr[rs].minn);
}
void build(int l,int r,int rt)
{
    tr[rt].l=l,tr[rt].r=r;
    tr[rt].lazy=0;
    tr[rt].minn=1e18;
    if(l==r) {tr[rt].minn=a[l];return;}
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    update(rt);
}
void pushdown(int rt)
{
    if(tr[rt].lazy)
    {
        tr[ls].lazy+=tr[rt].lazy;
        tr[rs].lazy+=tr[rt].lazy;
        tr[ls].minn+=tr[rt].lazy;
        tr[rs].minn+=tr[rt].lazy;
        tr[rt].lazy=0;
    }
}
void modify(int l,int r,int rt,int c)
{
    if(tr[rt].l==tr[rt].r)
    {
        tr[rt].lazy+=c;
        tr[rt].minn+=c;
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    pushdown(rt);
    if(l<=mid) modify(l,r,ls,c);
    if(r>mid) modify(l,r,rs,c);
    update(rt);
}
pair<int,int> query(int l,int r,int rt)
{
    if(tr[rt].l==tr[rt].r)
        return {tr[rt].minn,tr[rt].l};
    pushdown(rt);
    int ans=1e18,pos;
    int mid=tr[rt].l+tr[rt].r>>1;
    if(l<=mid)
    {
        auto [x,y]=query(l,r,ls);
        if(ans>x)
            ans=x;pos=y;
    }
    if(r>mid)
    {
        auto [x,y]=query(l,r,rs);
        if(ans>x) ans=x,pos=y;
    }
    update(rt);
    return {ans,pos};
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    vector<pair<int,int>> q;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        q.push_back({x,y});
        modify(1,x,1,-y);
    }
    sort(q.begin(),q.end(),greater<>());
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        auto [x,y]=query(1,n,1);
        ans+=x;
        modify(y,y,1,1e18);
        while(q.size() && q.back().first>=y)
        {
            auto [c,d]=q.back();q.pop_back();
            modify(1,c,1,d);
        }
        cout<<ans<<' ';
    }
    cout<<endl;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}