// https://contest.ucup.ac/submission/191340

#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <random>
#include <vector>
using namespace std;
template <typename T>
struct BIT {
  int n;
  vector<T> bit;
  BIT(int n_ = 0) : n(n_), bit(n_ + 1) {}
  T sum(int i) {
    T ans = 0;
    for (; i > 0; i -= i & -i) ans += bit[i];
    return ans;
  }
  void add(int i, T a) {
    if (i == 0) return;
    for (; i <= n; i += i & -i) bit[i] += a;
  }
  int lower_bound(T k) {
    if (k <= 0) return 0;
    int ret = 0, i = 1;
    while ((i << 1) <= n) i <<= 1;
    for (; i; i >>= 1)
      if (ret + i <= n && bit[ret + i] < k) k -= bit[ret += i];
    return ret + 1;
  }
};
int N;
long long A[2 << 17], B[2 << 17], Ai[2 << 17];
vector<int> a;
BIT<int> cnt;
BIT<long long> sum;
void dfs(int l, int r, int li, int ri, vector<long long>& ret) {
  if (l >= r) {
    for (int i = li; i < ri; i++) cnt.add(Ai[i] + 1, 1), sum.add(Ai[i] + 1, A[i]);
    return;
  }
  int mid = (l + r) / 2;
  int midi = -1;
  for (int i = li; i < ri; i++) {
    cnt.add(Ai[i] + 1, 1);
    sum.add(Ai[i] + 1, A[i]);
    if (i >= mid) {
      int r = cnt.lower_bound(mid + 1);
      long long now = B[i];
      now += sum.sum(r - 1);
      int need = (mid + 1) - cnt.sum(r - 1);
      now += (long long)need * a[r - 1];
      if (ret[mid] >= now) {
        ret[mid] = now;
        midi = i;
      }
    }
  }
  for (int i = li; i < ri; i++) cnt.add(Ai[i] + 1, -1), sum.add(Ai[i] + 1, -A[i]);
  assert(midi != -1);
  dfs(l, mid, li, midi + 1, ret);
  cnt.add(Ai[midi] + 1, -1), sum.add(Ai[midi] + 1, -A[midi]);
  dfs(mid + 1, r, midi, ri, ret);
}
vector<long long> solve() {
  a = vector<int>(A, A + N);
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  for (int i = 0; i < N; i++) Ai[i] = lower_bound(a.begin(), a.end(), A[i]) - a.begin();
  cnt = BIT<int>(a.size());
  sum = BIT<long long>(a.size());
  vector<long long> ret(N, (long long)9e18);
  dfs(0, N, 0, N, ret);
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int m;
    cin >> N >> m;
    for (int i = N; i--;) {
      cin >> A[i];
      B[i] = 0;
    }
    while (m--) {
      int r, w;
      cin >> r >> w;
      B[N - r] -= w;
    }
    for (int i = 1; i < N; ++i) {
      B[i] += B[i - 1];
    }
    for (int i = 0; i < N; i++) {
      B[i] += A[i];
    }
    for (int i = 1; i < N; ++i) {
      B[i - 1] = B[i];
    }
    B[N - 1] = 1e18;
    vector<long long> ans = solve();
    rotate(ans.begin(), ans.end() - 1, ans.end());
    ans[0] = *min_element(B, B + N);
    for (int i = 0; i < N; i++) cout << ans[i] << " \n"[i + 1 == N];
  }
}