#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 s[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;

struct node{
    ll w,num;
    bool operator <(const node &A)const{
        return w>A.w;
    }
};
priority_queue <node> us;

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);
    ll sum=0;
    q.push({inf});
    
    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;
    }
    for (ll i=cnt;i>=1;i--)
    {
        s[i]=s[i+1]+w[i];
        us.push({-s[i]+a[mi[p[i]]],i});
    }
    ll pre=cnt+1;
    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;
        vector <ll> add;
        while (!us.empty()&&q.top().w>=us.top().w-del)
        {
            if (us.top().num>=pre)
            {
                us.pop();
                continue;
            }
            er=mi[p[us.top().num]];
            del=-s[us.top().num];
            for (ll i=p[us.top().num-1]+1;i<=p[pre-1];i++)
                add.pb(a[i]);
            pre=us.top().num;
            break;
        }
        //("er=%lld pre=%lld del=%lld\n",er,pre,del);
        for (auto z:add)
            q.push({z});
        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();
    while (!us.empty()) us.pop();
    for(int i=0;i<=cnt;++i)w[i]=0,s[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

1
6 3
9 14 12 1 5 4
4 3
2 5
1 9
*/