#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define eb emplace_back
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e5 + 10;
const int INF = 1e18;
int n, m;
int a[N], b[N], vis[N], p[N], q[N];
void solve() {
  n = read(); m = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  for(int i = 1; i <= n; i++)b[i] = 0;
  for(int i = 1; i <= m; i++) {
    int r = read(), w = read();
    b[r] -= w;
  }
  for(int i = 1; i <= n; i++)vis[i] = false;
  for(int i = n - 1; i; i--)b[i] += b[i + 1];
  for(int i = 1; i <= n; i++)b[i] += a[i];
  for(int i = 1; i <= n; i++)p[i] = q[i] = i;
  sort(p + 1, p + 1 + n, [&](int x, int y) {return a[x] < a[y];});
  sort(q + 1, q + 1 + n, [&](int x, int y) {return b[x] < b[y];});
  int res = 0, pos = 0;
  for(int i = 1, j = 1, k = 1; i <= n; i++) {
    if(i == 1)res += b[q[k]], pos = q[k], vis[pos] = true, k++;
    else {
      while(j <= n && vis[p[j]])j++;
      while(k <= n && vis[q[k]])k++;
      int v1 = a[p[j]], v2 = a[pos] - b[pos] + b[q[k]];
      if(v1 < v2)res += v1, vis[p[j]] = true;
      else res += v2, pos = q[k], vis[q[k]] = true;
    }
    printf("%lld ", res);
  }
  putchar('\n');
  return ;
}
signed main() {
  int test = read();
  while(test--)solve();
  return 0;
}