#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f64 = double_t;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  for (int ti = 0; ti < t; ti += 1) {
    int n, m;
    cin >> n >> m;
    vector<i64> a(n + 1);
    vector<pair<int, int>> rw(m);
    vector<i64> tag(n << 2), mn(n << 2);
    for (int i = 1; i <= n; i += 1) { cin >> a[i]; }
    for (auto &[r, w] : rw) { cin >> r >> w; }
    function<void(int, int, int)> build = [&](int p, int tl, int tr) {
      int tm = midpoint(tl, tr);
      if (tl == tr) {
        mn[p] = a[tm];
      } else {
        build(p * 2, tl, tm);
        build(p * 2 + 1, tm + 1, tr);
        mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
      }
    };
    build(1, 1, n);
    auto push = [&](int p) {
      mn[p * 2] += tag[p];
      tag[p * 2] += tag[p];
      mn[p * 2 + 1] += tag[p];
      tag[p * 2 + 1] += tag[p];
      tag[p] = 0;
    };
    auto add = [&](int l, int r, i64 w) {
      function<void(int, int, int)> rec = [&](int p, int tl, int tr) {
        int tm = midpoint(tl, tr);
        if (tl >= l and tr <= r) {
          mn[p] += w;
          tag[p] += w;
        } else {
          push(p);
          if (l <= tm) { rec(p * 2, tl, tm); }
          if (r > tm) { rec(p * 2 + 1, tm + 1, tr); }
          mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
        }
      };
      rec(1, 1, n);
    };
    for (auto [r, w] : rw) { add(1, r, -w); }
    function<int(int, int, int)> find = [&](int p, int tl, int tr) {
      int tm = midpoint(tl, tr);
      if (tl == tr) { return tm; }
      push(p);
      if (mn[p * 2] <= mn[p * 2 + 1]) { return find(p * 2, tl, tm); }
      return find(p * 2 + 1, tm + 1, tr);
    };
    i64 ans = 0;
    for (int i = 1; i <= n; i += 1) {
      ans += mn[1];
      cout << ans << " ";
      int j = find(1, 1, n);
      while (not rw.empty() and rw.back().first >= j) {
        auto [r, w] = rw.back();
        rw.pop_back();
        add(1, r, w);
      }
      add(j, j, 1E18);
    }
    cout << "\n";
  }
}