#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
	return x*f;
}
const int N=2e5+5;
int n,m;
int a[N],b[N],id[N];
int root[N],tot;
int tree[N<<6],sum[N<<6],son[N<<6][2];
inline void update(int x){
	tree[x]=tree[ls]+tree[rs];
	sum[x]=sum[ls]+sum[rs];
	return;
}
void modify(int &x,int y,int l,int r,int w,int v){
	if(!x)x=++tot;
	if(l==r)return tree[x]+=1,sum[x]+=v,void();
	if(w<=mid)rs=son[y][1],modify(ls,son[y][0],l,mid,w,v);
	else ls=son[y][0],modify(rs,son[y][1],mid+1,r,w,v);
	update(x);
}
int query(int x,int l,int r,int L,int R){
	if(!x)return 0;
	if(L<=l&&r<=R)return tree[x];
	int cnt=0;
	if(L<=mid)cnt+=query(ls,l,mid,L,R);
	if(R>mid)cnt+=query(rs,mid+1,r,L,R);
	return cnt;
}
int ask(int x,int l,int r,int L,int R){
	if(!x)return 0;
	if(L<=l&&r<=R)return sum[x];
	int cnt=0;
	if(L<=mid)cnt+=ask(ls,l,mid,L,R);
	if(R>mid)cnt+=ask(rs,mid+1,r,L,R);
	return cnt;
}
int ask(int L,int R,int k){
	if(R-L+1<k)return 1e18;
	int l=0,r=n;
	while(l<r){
		if(query(root[mid],1,n,L,R)>=k)r=mid;
		else l=mid+1;
	}
	return ask(root[r],1,n,L,R);
}
void Init(){
	while(tot)tree[tot]=sum[tot]=son[tot][0]=son[tot][1]=0,tot--;
	n=read(),m=read();
	for(int i=1;i<=n;i++)b[i]=0;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++){
		int r=read(),x=read();
		b[1]+=x,b[r+1]-=x;
	}
	for(int i=1;i<=n;i++)b[i]+=b[i-1];
	for(int i=1;i<=n;i++)id[i]=i;
	sort(id+1,id+n+1,[](int A,int B){return a[A]<a[B];});
	for(int i=1;i<=n;i++)root[i]=0;
	for(int i=1;i<=n;i++)
		modify(root[i],root[i-1],1,n,id[i],a[id[i]]);
}
int ans[N];
void sol(int l,int r,int L,int R){
	if(l>r)return;
	if(L==r){
		for(int i=l;i<=r;i++)
			ans[i]=a[L]-b[L]+ask(L+1,n,i-1);
		return;
	}
	int cnt=a[L]-b[L]+ask(L+1,n,mid-1),minn=L;
	for(int i=L+1;i<=R;i++){
		int res=a[i]-b[i]+ask(i+1,n,mid-1);
		if(res<cnt)cnt=res,minn=i;
	}
	ans[mid]=cnt;
	sol(l,mid-1,minn,R);
	sol(mid+1,r,L,minn);
}
signed main(){
	int T=read();
	while(T--){
		Init();
		sol(1,n,1,n);
		for(int i=1;i<=n;i++)printf("%lld ",ans[i]);printf("\n");
	}
	return 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
*/