#include <bits/stdc++.h>

using namespace std;

const int N = 2e5;
const int M = 20 * N;

int root[N], ls[M], rs[M], sum[M], cnt[M], tsz;

void Modify(int& x, int y, int l, int r, int p, int v) {
  x = ++tsz;
  ls[x] = ls[y];
  rs[x] = rs[y];
  sum[x] = sum[y] + v;
  cnt[x] = cnt[y] + 1;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    Modify(ls[x], ls[y], l, mid, p, v);
  } else {
    Modify(rs[x], rs[y], mid + 1, r, p, v);
  }
}

int Walk(int x, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int mid = l + r >> 1;
  if (cnt[ls[x]] >= k) {
    return Walk(ls[x], l, mid, k);
  } else {
    return Walk(rs[x], mid + 1, r, k - cnt[ls[x]]);
  }
}

long long Query(int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return sum[x];
  }
  int mid = l + r >> 1;
  if (qr <= mid) {
    return Query(ls[x], l, mid, ql, qr);
  } else if (ql > mid) {
    return Query(rs[x], mid + 1, r, ql, qr);
  } else {
    return Query(ls[x], l, mid, ql, qr) + Query(rs[x], mid + 1, r, ql, qr);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> r(m), w(m);
    for (int i = 0; i < m; i++) {
      cin >> r[i] >> w[i];
      --r[i];
    }
    vector<long long> suff(n);
    for (int i = 0; i < m; i++) {
      suff[r[i]] += w[i];
    }
    for (int i = n - 2; i >= 0; i--) {
      suff[i] += suff[i + 1];
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return a[i] < a[j];
    });
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
      pos[order[i]] = i;
    }
    while (tsz > 0) {
      ls[tsz] = 0;
      rs[tsz] = 0;
      sum[tsz] = 0;
      cnt[tsz] = 0;
      tsz--;
    }
    for (int i = n - 1; i >= 0; i--) {
      if (i + 1 == n) {
        root[i] = 0;
      } else {
        root[i] = root[i + 1];
      }
      Modify(root[i], root[i], 0, n - 1, pos[i], a[i]);
    }
    auto F = [&](int k, int i) {
      if (n - i < k) {
        return (long long) 1e18;
      }
      if (k == 1) {
        return a[i] - suff[i];
      }
      int p = Walk(root[i + 1], 0, n - 1, k - 1);
      return a[i] - suff[i] + Query(root[i + 1], 0, n - 1, 0, p);
    };
    vector<long long> res(n + 1);
    function<void(int, int, int, int)> Solve = [&](int l, int r, int L, int R) {
      if (l > r) {
        return;
      }
      int mid = l + r >> 1;
      int opt = L;
      long long val = F(mid, L);
      for (int i = L + 1; i <= R; i++) {
        long long cur = F(mid, i);
        if (cur < val) {
          val = cur;
          opt = i;
        }
      }
      res[mid] = val;
      Solve(l, mid - 1, opt, R);
      Solve(mid + 1, r, L, opt);
    };
    Solve(1, n, 0, n - 1);
    for (int i = 1; i <= n; i++) {
      cout << res[i] << " ";
    }
    cout << '\n';
  }
  return 0;
}