#include <bits/stdc++.h>
#define w first
#define idx second

typedef long long ll;


void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1);
    std::vector<ll> cep(n + 2, 0);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int r, w;
        std::cin >> r >> w;
        cep[1] -= w;
        cep[r + 1] += w;
    }
    for (int i = 1; i <= n; i++) {
        cep[i] += cep[i - 1];
    }
    std::vector<std::pair<int, int>> pre(n + 1);
    pre[0] = {0x3f3f3f3f, 0};
    for (int i = 1; i <= n; i++) {
        if (pre[i - 1].w >= a[i] + cep[i]) {
            pre[i] = {a[i] + cep[i], i};
        } else {
            pre[i] = pre[i - 1];
        }
    }
    std::multiset<int> s; 
    int tmp = n + 1; 
    ll hav_use = 0, sum = 0;
    std::vector<ll> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        if ((!s.empty()) && *s.begin() <= pre[tmp - 1].w + hav_use) {
            sum += *s.begin();
            s.erase(s.begin());
            ans[i] = sum;
            continue;
        }
        int nex = pre[tmp - 1].idx;
        for (int j = nex + 1; j < tmp; j++) {
            s.insert(a[j]);
        }
        sum += pre[tmp - 1].w + hav_use;
        hav_use -= hav_use + cep[nex];
        tmp = nex;
        ans[i] = sum;
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }
}

int main() {

#ifdef Onlion_Judge
    freopen("IO/input.in", "r", stdin);
    freopen("IO/output.out", "w", stdout);
    // freopen("E:\\save work\\data\\4.in", "w", stdout);
#endif

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
}