/*******************************
| Author:  Cai_Guang
| Problem: 游游的选数乘积
| Contest: NowCoder
| URL:     https://ac.nowcoder.com/acm/contest/69733/D
| When:    2023-11-09 23:18:40
| 
| Memory:  524288 MB
| Time:    2000 ms
*******************************/

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

struct SegmentTree {
    int n;
    vector<int> a;
    struct Node {
        int mi = 1e17, add, mip = 0;
    };
    vector<Node> tr;

    SegmentTree(int _n, vector<int> &a) : tr(4 * _n), n(_n) {
        this -> a = a;
        build(1, 1, n);
    }
    void build(int u, int L, int R) {
        int mid = L + R >> 1;
        if (L == R) {
            tr[u].mi = a[L];
            tr[u].mip = L;
            return;
        }
        build(u << 1, L, mid);
        build(u << 1 | 1, mid + 1, R);
        pushup(u, L, R);
    }
    void add(int u, int L, int R, int l, int r, int x) {
        int mid = L + R >> 1;
        if (l <= L && R <= r) {
            tr[u].mi += x;
            tr[u].add += x;
            return; 
        }
        pushdown(u, L, R);
        if (l <= mid) {
            add(u << 1, L, mid, l, r, x);
        }
        if (r >= mid + 1) {
            add(u << 1 | 1, mid + 1, R, l, r, x);
        }
        pushup(u, L, R);
    }  
    void pushdown(int u, int L, int R) {
        tr[u << 1].add += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add;
        tr[u << 1].mi += tr[u].add;
        tr[u << 1 | 1].mi += tr[u].add;
        tr[u].add = 0;
    } 
    void pushup(int u, int L, int R) {
        if (tr[u << 1].mi <= tr[u << 1 | 1].mi) {
            tr[u].mi = tr[u << 1].mi;
            tr[u].mip = tr[u << 1].mip;
        } else {
            tr[u].mi = tr[u << 1 | 1].mi;
            tr[u].mip = tr[u << 1 | 1].mip;
        }
    }
    void modify(int u, int L, int R, int p, int x) {
        int mid = L + R >> 1;
        if (L == R && L == p) {
            tr[u].mi = x;
            return; 
        }
        pushdown(u, L, R);
        if (p <= mid) {
            modify(u << 1, L, mid, p, x);
        }
        if (p >= mid + 1) {
            modify(u << 1 | 1, mid + 1, R, p, x);
        }
        pushup(u, L, R);
    }
    pair<int, int> query(int u, int L, int R, int l, int r) {
    	// cout << u << ' ' << L << ' ' << R << " " << l << ' ' << r << '\n';
        int mid = L + R >> 1;
        if (l <= L && R <= r) {
            return {tr[u].mi, tr[u].mip};
        }
        pushdown(u, L, R);
        int resmi = 1e18, resmip = 0;
        if (l <= mid) {
            auto tmp = query(u << 1, L, mid, l, r);
            if (tmp.first < resmi) {
                resmi = tmp.first;
                resmip = tmp.second;
            }
        }
        if (r > mid) {
            auto tmp = query(u << 1 | 1, mid + 1, R, l, r);
            if (tmp.first < resmi) {
                resmi = tmp.first;
                resmip = tmp.second;
            }    
        }
        pushup(u, L, R);
        // cout << "ISISISIS" << resmi << ' ' << resmip << '\n';
        return {resmi, resmip};
    }
    void add(int l, int r, int x) {
        add(1, 1, n, l, r, x);
    }
    void modify(int p, int x) {
        modify(1, 1, n, p, x);
    }
    pair<int, int> query(int l, int r) {
        return query(1, 1, n, l, r);
    }
};



void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	vector<pii> xy(m + 1);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	SegmentTree tree(n, a);
	for(int i = 1; i <= m; i++) {
		// cin >> x[i] >> y[i];
		auto &[x, y] = xy[i];
		cin >> x >> y;
		tree.add(1, x, -y);
	}
	sort(xy.begin() + 1, xy.end());
	int mi = 1;
	// for(int i = 1; i <= n; i++) {
	// 	cout << tree.query(i, i).first << ' ';
	// } cout << endl;
	for(int i = 1; i <= n; i++) {
		// cout << i << endl;
		auto [x, y] = tree.query(1, n);
		ans += x;
		for(; mi <= m; mi++) {
			tree.add(1, xy[mi].first, xy[mi].second);
		}
		// cout << "I Y " << i << ' ' << x << ' ' << y << endl;
		tree.modify(y, 1e18);
		cout << ans << ' ';
		// cout << i << endl;
	} cout << '\n';
	// cout << ans / 2 << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

// #ifdef Cai_Guang
// 	freopen("1.in", "r", stdin);
// #endif
	
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
}