#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll n,a[MAXN],r[MAXN],w[MAXN],ind[MAXN],indd,pref[MAXN],ans[MAXN],root[MAXN],L[MAXN],R[MAXN];
pair<ll,ll> val[19*MAXN];
void Build(ll x,ll lx,ll rx)
{
    if (lx==rx)
        return;
    ll mid=(lx+rx)/2;
    L[x]=indd;
    Build(indd++,lx,mid);
    R[x]=indd;
    Build(indd++,mid+1,rx);
}
void Add(ll pos,pair<ll,ll> vall,ll prevx,ll x,ll lx,ll rx)
{
    if (lx==rx)
    {
        val[x]=vall;
        return;
    }
    ll mid=(lx+rx)/2;
    if (pos<=mid)
    {
        L[x]=indd++;
        R[x]=R[prevx];
        Add(pos,vall,L[prevx],L[x],lx,mid);
    }
    else
    {
        L[x]=L[prevx];
        R[x]=indd++;
        Add(pos,vall,R[prevx],R[x],mid+1,rx);
    }
    val[x]={val[L[x]].first+val[R[x]].first,val[L[x]].second+val[R[x]].second};
}
ll Find(ll vall,ll x,ll lx,ll rx)
{
    if (!vall)
        return 0;
    if (lx==rx)
        return val[x].second;
    ll mid=(lx+rx)/2;
    if (val[L[x]].first>=vall)
        return Find(vall,L[x],lx,mid);
    return val[L[x]].second+Find(vall-val[L[x]].first,R[x],mid+1,rx);
}
void Solve(ll L,ll R,ll A,ll B)
{
    if (L>R)
        return;
    ll f,mid=(L+R)/2,minn=LLONG_MAX;
    for (ll i=B;i>=A;i--)
    {
        if (n-i+1>=mid)
        {
            ll anss=Find(mid-1,root[i+1],1,n);
            if (anss+a[i]-pref[i]<minn)
            {
                minn=anss+a[i]-pref[i];
                f=i;
            }
        }
    }
    ans[mid]=minn;
    Solve(L,mid-1,f,B);
    Solve(mid+1,R,A,f);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll t,m;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        vector<pair<ll,ll> > v;
        for (ll i=1;i<=n;i++)
        {
            cin >> a[i];
            v.push_back({a[i],i});
            pref[i]=0;
        }
        pref[n+1]=0;
        for (ll i=1;i<=m;i++)
        {
            cin >> r[i] >> w[i];
            pref[r[i]]+=w[i];
        }
        for (ll i=n;i>0;i--)
            pref[i]+=pref[i+1];
        sort(v.begin(),v.end());
        for (ll i=0;i<n;i++)
            ind[v[i].second]=i+1;
        root[n+1]=1;
        indd=2;
        Build(1,1,n);
        for (ll i=n;i>0;i--)
        {
            root[i]=indd++;
            Add(ind[i],{1,a[i]},root[i+1],root[i],1,n);
        }
        Solve(1,n,1,n);
        for (ll i=1;i<=n;i++)
            cout << ans[i] << " ";
        cout << "\n";
    }
    return 0;
}