#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

template<typename T> class segtree {
private:
    int n,sz,h;
    vector<pair<T, int> > node;
    vector<T> lazy;
    void eval(int k) {
        if(lazy[k]){
            node[k].first += lazy[k];
            if(k < n) {
                lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

public:
    segtree(const vector<T>& v) : sz((int)v.size()), h(0) {
        n = 1;
        while(n < sz) n *= 2, h++;
        node.resize(2*n, pair<T, int>(numeric_limits<T>::max(), sz));
        lazy.resize(2*n, 0);
        for(int i = 0; i < sz; i++){
            node[i+n] = make_pair(v[i], i);
        }
        for(int i = n-1; i >= 1; i--){
            node[i] = min(node[2*i], node[2*i+1]);
        }
    }
    void range(int a, int b, T x, int k=1, int l=0, int r=-1){
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b){
            lazy[k] += x;
            eval(k);
        }else{
            range(a, b, x, 2*k, l, (l+r)/2);
            range(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = min(node[2*k], node[2*k+1]);
        }
    }
    pair<T, int> query(int a, int b) {
        a += n, b += n - 1;
        for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
        b++;
        pair<T, int> res1 = make_pair(numeric_limits<T>::max(), sz);
        pair<T, int> res2 = make_pair(numeric_limits<T>::max(), sz);
        while(a < b) {
            if(a & 1) eval(a), res1 = min(res1, node[a++]);
            if(b & 1) eval(--b), res2 = min(res2, node[b]);
            a >>= 1, b >>= 1;
        }
        return min(res1, res2);
    }
    void print() {
        for(int i = 0; i < sz; i++){
            pair<T,int> p;
            p = query(i,i+1);
            cout << "st[" << i << "]: " << p.first << " " << p.second << endl;
        }
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    while (q--) {
        int n,m; cin >> n >> m;
        vector<ll> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        vector<ll> c(n+1);
        priority_queue<pair<ll,ll>> pq;
        for (int i = 0; i < m; ++i) {
            ll r,rr; cin >> r >> rr;
            pq.push({-r, rr});
            c[0] += rr;
            c[r] -= rr;
        }
        for (int i = 0; i < n; ++i) {
            c[i+1] += c[i];
        }
        vector<ll> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = a[i] - c[i];
        }
        segtree<ll> seg = segtree(v);
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
//            seg.print();
            auto u = seg.query(0, n);
            int j = u.second;
            sum += u.first;
            cout << sum << " ";
            ll dif = a[j]-u.first;
            while (dif and pq.size()) {
                auto p = pq.top(); pq.pop();
                int r = -p.first;
                seg.range(0, r, p.second);
                dif -= p.second;
            }
            seg.range(j, j+1, 1e18);
        }
        cout << "\n";
    }
}