#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define Ma 500005
#define G 3
#define N 13
#define pb push_back
#define L (1<<21)
using namespace std;
ll inf=1e18;
ll mi[Ma];
ll a[Ma];
ll p[Ma],w[Ma];
ll n,m;

struct Go{
    ll num,w;
}t[Ma];


struct pri{
    ll w;
    bool operator <(const pri &A)const{
        return w>A.w;
    }
};
priority_queue <pri> q,qq;

void sol()
{
    cin>>n>>m;
    mi[0]=inf;
    for (ll i=1;i<=n;i++)
        cin>>a[i],mi[i]=min(mi[i-1],a[i]);
    for (ll i=1;i<=m;i++)
        cin>>t[i].num>>t[i].w,t[i].num=min(t[i].num,n),p[i]=t[i].num;
    sort(p+1,p+m+1);
    ll cnt=unique(p+1,p+m+1)-(p+1);
    for (ll i=1;i<=m;i++)
    {
        ll l=lower_bound(p+1,p+cnt+1,t[i].num)-p;
        w[l]+=t[i].w;
    }
    ll pre=cnt;
    for (ll i=p[cnt]+1;i<=n;i++)
        q.push({a[i]});
    ll ans=0,del=0;
    for (ll ca=1;ca<=n;ca++)
    {
        ll er=-1;
        while (q.empty())
        {
            del+=w[pre],pre--;
            for (ll i=p[pre]+1;i<=p[pre+1];i++)
                q.push({a[i]});
        }
        while (pre!=0&&q.top().w>=mi[p[pre]]-w[pre])
        {
            er=mi[p[pre]];
            del+=w[pre],pre--;
            for (ll i=p[pre]+1;i<=p[pre+1];i++)
                q.push({a[i]});
        }

        //("ca=%lld pre=%lld er=%lld\n",ca,pre,er);
        if (er==-1)
            ans+=q.top().w,q.pop();
        else
            ans+=er,qq.push({er});
        while (!q.empty()&&!qq.empty()&&q.top().w==qq.top().w)
            q.pop(),qq.pop();
        cout<<ans-del<<" \n"[ca==n];
    }
    while(!q.empty())q.pop();
    while (!qq.empty()) qq.pop();
    for(int i=0;i<=cnt;++i)w[i]=0;
}


int	main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int tt=1;
    cin>>tt;
    while (tt--)
        sol();
    return 0;
}
/*
500000 500000
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

 1
 5 2
 3 5 2 1 1
 2 2
 3 1
*/