#include<bits/stdc++.h>
//#define Debug
using std::vector;
using std::pair;
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
template<typename T>
void Clear(T&x){T y;x.swap(y);}
template<typename... Args>
void Clear(Args&... args){
    (Clear(args), ...);//必须加括号
}
std::default_random_engine E(std::chrono::steady_clock().now().time_since_epoch().count());

void Solve(){
	int n,m;scanf("%d%d",&n,&m);
	vector<ll>Arr;Arr.resize(n+10);
	vector<ll>Wrr;Wrr.resize(m+10);
	for(int i=1;i<=n;i++)
		scanf("%lld",&Arr[i]);
	for(int i=1;i<=m;i++){
		long long x;int y;
		scanf("%d",&y);
		scanf("%lld",&x);
		Wrr[y]+=x;
	}
	for(int i=n-1;i>=1;i--)
		Wrr[i]+=Wrr[i+1];
	std::set<pair<ll,int>>S;
	for(int i=1;i<=n;i++){
		S.insert({Arr[i]-Wrr[i],i});
	}
	std::priority_queue<int,vector<int>,std::greater<int>>Q;
	ll ans=0,tmp=0;
	int last=n+1;
	
	auto Relieve=[&](int h,int t){
		for(int i=h;i!=t;i++){
			S.erase({Arr[i]-Wrr[i],i});
			if(i!=h)Q.push(Arr[i]);
		}
	};
	
	for(int i=1;i<=n;i++){
		if(!S.empty()){
			auto k=*S.begin();
			if(!Q.empty()){
				ll p=Q.top();
				if(k.fi+tmp<=p){
					ans+=k.fi+tmp;
					Relieve(k.se,last);
					last=k.se;
					tmp=Wrr[k.se];
				}
				else{
					ans+=Q.top();
					Q.pop();
				}
			}
			else{
				ans+=k.fi+tmp;
				Relieve(k.se,last);
				last=k.se;
				tmp=Wrr[k.se];
			}
		}
		else{
			ans+=Q.top();
			Q.pop();
		}
		printf("%lld ",ans);
	}
	puts("");
}


int main(){
	#ifdef LOCAL
	freopen("In.txt","r",stdin);
	freopen("Out.txt","w",stdout);
	#endif
	int Task=1;scanf("%d",&Task);
	for(int Case=1;Case<=Task;Case++){
		Solve();
	}
	return 0;
}