#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node {
	int r;
	ll w;
};
istream& operator >> (istream & in, struct node & tmp) {
	in >> tmp.r >> tmp.w;
	return in;
}
struct aa {
	ll a;
	int j;
	bool operator > (const struct aa & y) const {
		return a > y.a;
	}
};
void solve(int t) {
	int n, m;
	cin >> n >> m;
	vector<ll> a(n + 30);
	vector<node> b(m + 30);
	int i;
	for(i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for(i = 1; i <= m; ++i) {
		// cin >> b[i];
		cin >> b[i].r >> b[i].w;
	}
	sort(b.begin() + 1, b.begin() + 1 + m, [&](struct node x, struct node y) {
		return x.r <= y.r;
	});
	// priority_queue<aa, vector<aa>, greater<aa>> q;
	priority_queue<ll, vector<ll>, greater<ll>> qq;
	int now = 0;
	for(i = 1; i <= m; ++i) {
		for(int j = now + 1; j <= b[i].r; ++j) {
			// q.push((aa){a[j], j});
			qq.push(a[j]);
		}
		// printf("%d , %d[\n", now, b[i].r);
		now = b[i].r;
		// cout << q.empty() << "???\n";
		if(qq.empty()) {
			while(1);
			// exit(0);
		}
		auto topp = qq.top();
		// cout << topp.a << "qwq\n";
		qq.pop();
		// topp.a -= b[i].w;
		topp -= b[i].w;
		qq.push(topp);
	}
	for(int j = now + 1; j <= n; ++j) {
		// q.push((aa){a[j], j});
		qq.push(a[j]);
	}
	// printf("%d, %d [\n", now, n);
	vector<ll> ans(n + 30);
	i = 0;
	ans[0] = 0;
	for(i = 1; i <= n; ++i) {
		if(qq.empty())
			while(1);
		// ans[i] = ans[i - 1] + q.top().a;
		ans[i] = ans[i - 1] + qq.top();
		qq.pop();
		// cout << q.empty() << '\n';
		// cout << ans[i] << " \n"[i == n];
		cout << ans[i];
		if(i < n)
			cout << " ";
	}
	if(t > 0)
		cout << "\n";
	return;
}
int main() {
	int t;
	cin >> t;
	while(t--) {
		solve(t);
	}
	return 0;
}