#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+6;
#define ll long long
#define il long long

void solve()
{
	ll n,m;
	cin>>n>>m;
	ll res=0;
	vector<ll>a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	set<pair<ll,int>>s;
	vector<pair<int,int>>b(m+1);
	vector<ll>sum(n+1);
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		b[i]={x,y};
		sum[1]+=y;
		sum[x+1]-=y;
	}
	sort(b.begin()+1,b.end());
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	int now=1;
	for(int i=1;i<=n;i++){
		s.insert({a[i],i});
		while(now<=n&&b[now].first==i){
			auto it=*s.begin();
			s.erase(it);
			it.first-=b[now].second;
			s.insert(it);
			now++;
		}
	}
	for(auto it:s){
		res+=it.first;
		cout<<res<<" ";
	}
	cout<<'\n';
	
}
int  main(){
	ios::sync_with_stdio(false);	
	int t=1;
	cin>>t;
	//ll res=1;
	//for(int i=1;i<=13;i++)res*=i;
	//cout<<res<<'\n';
	while(t--)solve();
	return 0;
}