#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0;bool f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    if(f)return x;return ~(x-1);
}
int T,n,m,cnt,tot,a[200005],lsh[200005],rt[200005];
ll c[200005],ans[200005];
struct{
	int l,r,cnt;ll v;
}t[4000005];
void ins(int &p,int q,int l,int r,int d){
	if(!p)p=++tot;
	t[p]=t[q];
	t[p].cnt++,t[p].v+=lsh[d];
	if(l==r)return;
	int mid=l+r>>1;
	if(d<=mid)ins(t[p].l,t[q].l,l,mid,d);
	else ins(t[p].r,t[q].r,mid+1,r,d);
}
ll ask(int p,int q,int l,int r,int k){
	if(l==r)return 1ll*min(t[p].cnt-t[q].cnt,k)*lsh[l];
	int mid=l+r>>1;
	if(k<=t[t[p].l].cnt-t[t[q].l].cnt)return ask(t[p].l,t[q].l,l,mid,k);
	return t[t[p].l].v-t[t[q].l].v+ask(t[p].r,t[q].r,mid+1,r,k-t[t[p].l].cnt+t[t[q].l].cnt);
}
void solve(int l,int r,int L,int R){
	if(l>r)return;
	int mid=l+r>>1,p=0;ans[mid]=1e18;
	for(int i=L;i<=R;i++)if(n-i+1>=mid){
		ll tmp=c[i]+lsh[a[i]]+ask(rt[n],rt[i],1,cnt,mid-1);
		if(ans[mid]>tmp)ans[mid]=tmp,p=i;
	}
	solve(l,mid-1,p,R),solve(mid+1,r,L,p);
}
int main(){
	T=read();
	while(T--){
		tot=cnt=0;
		n=read(),m=read();
		for(int i=1;i<=n;i++)a[i]=read(),c[i]=rt[i]=0,lsh[++cnt]=a[i];
		while(m--){
			int x=read(),y=read();
			c[1]-=y,c[x+1]+=y;
		}
		for(int i=1;i<=n;i++)c[i]+=c[i-1];
		sort(lsh+1,lsh+cnt+1);
		cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
			ins(rt[i],rt[i-1],1,cnt,a[i]);
		}
		solve(1,n,1,n);
		for(int i=1;i<=n;i++)cout<<ans[i]<<" ";puts("");
	}
}