#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int inf=1e9+10; 
struct t{
	int x,y;
	bool operator <(t _){
		return x<_.x;
	}
}b[maxn];
struct node{
	int l,r,val,id,tag;
}tr[maxn*4];
int n,a[maxn],m;
int ls(int u){
	return (u<<1);
}
int rs(int u){
	return (u<<1)|1;
}
bool inrange(int L,int R,int l,int r){
	return (L<=l)&&(r<=R);
}
bool outofrange(int L,int R,int l,int r){
	return (R<l)||(r<L);
}
void pushup(int u){
	if(tr[u].l==tr[u].r) return ;
	if(tr[ls(u)].val<tr[rs(u)].val) tr[u].val=tr[ls(u)].val,tr[u].id=tr[ls(u)].id;
	else tr[u].val=tr[rs(u)].val,tr[u].id=tr[rs(u)].id;
}
void build(int u,int l,int r){
	tr[u].l=l;
	tr[u].r=r;
	tr[u].tag=0;
	if(l==r){
		tr[u].val=a[l];
		tr[u].id=l;
		return ;
	}
	int mid=l+r>>1;
	build(ls(u),l,mid),build(rs(u),mid+1,r);
	pushup(u); 
}
void pushdown(int u){
	if(tr[u].l==tr[u].r||tr[u].tag==0) return ;
	int k=tr[u].tag;tr[u].tag=0;
	tr[ls(u)].tag+=k,tr[rs(u)].tag+=k;
	tr[ls(u)].val+=k,tr[rs(u)].val+=k; 
}
void update(int u,int l,int r,int k){
	if(tr[u].tag) pushdown(u);
	if(inrange(l,r,tr[u].l,tr[u].r)){
		tr[u].tag+=k;
		tr[u].val+=k;
		pushdown(u);
	}
	else if(!outofrange(l,r,tr[u].l,tr[u].r)){
		update(ls(u),l,r,k),update(rs(u),l,r,k);
	}
	pushup(u);
}
void ban(int u,int x){
	if(tr[u].l==tr[u].r) return (void)(tr[u].val=inf);
	if(tr[u].tag) pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) ban(ls(u),x);
	else ban(rs(u),x);
	pushup(u);
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i].x>>b[i].y;
	sort(b+1,b+m+1),build(1,1,n);
	for(int i=1;i<=m;i++) update(1,1,b[i].x,-b[i].y);
	int z=1,res=0;
	for(int i=1;i<=n;i++){
		int minn=tr[1].val,mini=tr[1].id;
		ban(1,mini),res+=minn;
		while(b[z].x>=mini&&z<=m) update(1,1,b[z].x,b[z].y),z++;
		cout<<res<<" ";
	}
	cout<<endl;
}
signed main(){
 	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	cin>>t;
	while(t--) solve();
	return 0;
}