#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;

#define maxn 200005
ll n,m;
pll a[maxn];
ll b[maxn];
ll c[maxn];
bool cmp(pll x,pll y){
    if(x.fi!=y.fi) return x.fi<y.fi;
    return x.sc>y.sc;
}
ll ans[maxn];
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=n;i++) ans[i] = llinf;
    for(ll i = 1;i<=n;i++) a[i].sc = i;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi;
    for(ll i = 1;i<=n+1;i++) c[i] = 0;
    for(ll i = 1;i<=m;i++){
        ll r,w; cin >> r >> w;
        c[r+1]-=w;
        c[1]+=w;
    }
    for(ll i = 1;i<=n;i++) c[i]+=c[i-1];
    for(ll i = 1;i<=n;i++) b[i] = a[i].fi - c[i];
    for(ll i = 1;i<=n;i++) b[i] = min(b[i],b[i-1]);
    sort(a+1,a+1+n,cmp);
    ll sum = 0;
    ll l = n+1;
    for(ll i = 1;i<=n;i++){
        l = min(l,a[i].sc);
        sum+=a[i].fi;
        ans[i] = min(ans[i],sum-c[l]);
        if(l>1) ans[i+1] = sum + b[l-1];
    }
    for(ll i = 1;i<=n;i++) cout<<ans[i]<< " ";
    cout<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	cin >> t;
	while(t--){
		tc();
	}
	return (0-0);
}
/**
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
**/