#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }

ll N, M;
vector<ll> A;
vector<ll> B;
struct Window {
    ll first, cost;
    priority_queue<ll> lo;
    priority_queue<ll, vector<ll>, greater<>> hi;
    Window() {
        first = N - 1;
        cost = 0;
    }
    ll operator()(ll i, ll j) {
        assert(i >= lo.size());
        assert(j <= first);
        while (j < first) hi.push(A[first--]);
        if(lo.size() + hi.size() < i) return INF;
        while(lo.size() < i) {
            const ll x = hi.top();
            hi.pop();
            cost += x;
            lo.push(x);
        }
        while(lo.size() && hi.size() && lo.top() > hi.top()) {
            const ll x = lo.top(), y = hi.top();
            lo.pop(); hi.pop();
            lo.push(y); hi.push(x);
            cost += y - x;
        }
        return cost + B[first];
    }
};
void solve() {
    cin >> N >> M;
    A.resize(N);
    B.assign(N, 0);
    for(ll& a : A) cin >> a;
    while(M--) {
        ll r, w;
        cin >> r >> w;
        B[--r] += w;
    }
    for(ll i = N; --i; ) B[i - 1] += B[i];
    rep(i, 0, N) B[i] = A[i] - B[i];
    vector<ll> ans(N, INF);
    vector<Window> windows(30);
    auto mm = [&](ll x1, ll x2, ll y1, ll y2, ll d, auto mm) -> void {
        if(x1 > x2) return;
        auto& w = windows[d];
        const ll x3 = (x1 + x2) / 2;
        ll y3 = y1;
        for(ll y = y1; y >= y2; y--) if(chmin(ans[x3], w(x3, y))) y3 = y;
        mm(x1, x3 - 1, y1, y3, d + 1, mm);
        mm(x3 + 1, x2, y3, y2, d + 1, mm);
    };
    mm(0, N - 1, N - 1, 0, 0, mm);
    rep(i, 0, N) cout << ans[i] << " \n"[i + 1 == N];
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin >> T;
    while(T--) solve();
}