#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

const int N = 200010;
const int M = N * 30;

struct node {
  int cnt;
  ll sum;
  friend node operator+(node x, node y) {
    node res;
    res.cnt = x.cnt + y.cnt, res.sum = x.sum + y.sum;
    return res;
  }
} t[M];

int n, m, a[N], id[N], ls[M], rs[M], rt[N], tot;
pii c[N];
ll sum[N], ans[N];

#define mid ((l + r) >> 1)

void upd(int &p, int q, int l, int r, int x, int v) {
  p = ++tot, ls[p] = ls[q], rs[p] = rs[q];
  if (l == r) return t[p] = t[q], t[p].cnt++, t[p].sum += v, void();
  if (x <= mid) upd(ls[p], ls[q], l, mid, x, v);
  else upd(rs[p], rs[q], mid + 1, r, x, v);
  t[p] = t[ls[p]] + t[rs[p]];
}

ll qry(int p, int l, int r, int w) {
  if (l == r) return t[p].sum;
  if (w <= t[ls[p]].cnt) return qry(ls[p], l, mid, w);
  else return qry(rs[p], mid + 1, r, w - t[ls[p]].cnt) + t[ls[p]].sum;
}

#undef mid

void solve(int l, int r, int ql, int qr) {
  int mid = (l + r) >> 1;
  pll res = pll(1e18, -1);
  rep (i, ql, qr) {
    if (n - i + 1 < mid) continue;
    ll val = qry(rt[i], 1, n, mid) - sum[i];
    res = min(res, pll(val, i));
  }
  ans[mid] = res.fi;
  if (l != mid) solve(l, mid - 1, ql, res.se);
  if (r != mid) solve(mid + 1, r, res.se, qr);
}

void work() {
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i];
  rep (i, 0, n + 1) sum[i] = 0;
  rep (i, 1, m) {
    int x, y;
    cin >> x >> y;
    sum[x] += y;
  }
  per (i, n, 1) sum[i] += sum[i + 1];
  rep (i, 1, n) c[i] = pii(a[i], i);
  sort(c + 1, c + n + 1);
  rep (i, 1, n) id[i] = lower_bound(c + 1, c + n + 1, pii(a[i], i)) - c;
  rep (i, 1, tot) t[i] = (node){0, 0ll}, ls[i] = rs[i] = 0;
  tot = 0, rt[n + 1] = 0;
  per (i, n, 1) upd(rt[i], rt[i + 1], 1, n, id[i], a[i]);
  solve(1, n, 1, n);
  rep (i, 1, n) cout << ans[i] << " ";
  cout << "\n";
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}