/*
对于一个 k，求出在 i 或之后，最便宜的 k-1 个物品的价值和 f[k-1](i)，那么答案是：
	min(i){ v[i] - w[i] + f[k-1](i+1) }
随着 k 的增长，较靠后的 i 的答案会变大地更快。
决策单调性。v[i]-w[i] 可以取前缀 min。
需要维护数集，支持插入、k+=1、求前 k 小值之和。对顶堆？
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e16;
int n,m;
int v[210000],w[210000],mvw[210000];
struct Heaps
{
	priority_queue<int,vector<int>,less<int>> q;
	priority_queue<int,vector<int>,greater<int>> nq;
	int sum;
	void insert(int x)
	{
		// cout<<"Insert x="<<x<<endl;
		if(!q.empty()&&x<q.top())
		{
			sum+=x-q.top();
			nq.push(q.top());
			q.pop();
			q.push(x);
		}
		else
			nq.push(x);
	}
	void addK()
	{
		// cout<<"AddK add "<<nq.top()<<endl;
		sum+=nq.top();
		q.push(nq.top());
		nq.pop();
	}
	int sumIfInsert(int x)
	{
		// cout<<"SumIfInsert x="<<x<<" = "<<(!q.empty()&&x<q.top()?sum-q.top()+x:sum)<<endl;
		return !q.empty()&&x<q.top()?sum-q.top()+x:sum;
	}
};
Heaps q;
void clear()
{
	for(int i=0;i<=n+10;i++)
		v[i]=w[i]=mvw[i]=0;
	q.q=priority_queue<int,vector<int>,less<int>>();
	q.nq=priority_queue<int,vector<int>,greater<int>>();
	q.sum=0;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>v[i];
		for(int i=1;i<=m;i++)
		{
			int t,r;
			cin>>t>>r;
			w[t]+=r;
		}
		for(int i=n;i>=1;i--)
			w[i]+=w[i+1];
		for(int i=1;i<=n;i++)
		{
			mvw[i]=min<int>(mvw[i-1],v[i]-w[i]);
		}
		for(int k=1,i=n;k<=n;k++)
		{
			while(i>1&&mvw[i-1]+q.sumIfInsert(v[i])<=mvw[i]+q.sumIfInsert(inf))
				q.insert(v[i--]);
			// cout<<"k="<<k<<" : i="<<i<<endl;
			cout<<mvw[i]+q.sumIfInsert(inf)<<" ";
			while(n-i<k)
				q.insert(v[i--]);
			q.addK();
		}
		cout<<'\n';
		clear();
	}
}