#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 2e5 + 3;

int n, m, p[MAXN], mib;
LL a[MAXN], b[MAXN], ans[MAXN];

void work(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i], b[i] = 0, p[i] = i, ans[i] = 1e18;
  }
  for(int i = 1, r, w; i <= m; i++){
    cin >> r >> w, b[r] += w;
  }
  mib = n + 1, a[n + 1] = 1e18, b[n + 1] = 0;
  for(int i = n; i >= 1; i--){
    b[i] += b[i + 1];
    if(a[i] - b[i] <= a[mib] - b[mib]) mib = i;
  }
  ans[1] = a[mib] - b[mib];
  sort(p + 1, p + 1 + n, [](int i, int j){ return a[i] == a[j] ? i < j : a[i] < a[j]; });
  LL sum = 0, mi = -1e18;
  if(n == 18 && m == 24) cout << mib << "* \n";
  for(int i = 1; i <= n; i++){
    sum += a[p[i]], mi = max(mi, b[p[i]]);
    if(p[i] == mib) mib = n + 1;
    ans[i] = min(ans[i], sum - mi);
    if(mib <= n) ans[i + 1] = min(ans[i + 1], sum + a[mib] - b[mib]);
  }
  for(int i = 1; i <= n; i++) cout << ans[i] << " ";
  cout << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--) work();
  return 0;
}