#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
ll n,a[MAXN],r[MAXN],w[MAXN],pref[MAXN],ind[MAXN],ans[MAXN];
struct bit
{
    vector<ll> sum;
    void Init()
    {
        sum.resize(MAXN);
        fill(sum.begin(),sum.end(),0);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<MAXN;i+=i&(-i))
            sum[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=sum[i];
        return ans;
    }
};
bit C,S;
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--)
    {
        ll l=1,r=n,midd,anss=-1;
        while (l<=r)
        {
            midd=(l+r)/2;
            if (C.Calc(midd)<=mid-1)
            {
                anss=S.Calc(midd);
                l=midd+1;
            }
            else
                r=midd-1;
        }
        if (anss+a[i]-pref[i]<minn)
        {
            minn=anss+a[i]-pref[i];
            f=i;
        }
        C.Add(ind[i],1);
        S.Add(ind[i],a[i]);
    }
    ans[mid]=minn;
    for (ll i=A;i<=f;i++)
    {
        C.Add(ind[i],-1);
        S.Add(ind[i],-a[i]);
    }
    Solve(mid+1,R,A,f);
    for (ll i=f+1;i<=B;i++)
    {
        C.Add(ind[i],-1);
        S.Add(ind[i],-a[i]);
    }
    Solve(L,mid-1,f,B);
}
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];
        C.Init();
        S.Init();
        sort(v.begin(),v.end());
        for (ll i=0;i<n;i++)
            ind[v[i].second]=i+1;
        Solve(1,n,1,n);
        for (ll i=1;i<=n;i++)
            cout << ans[i] << " ";
        cout << "\n";
    }
    return 0;
}