#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <map>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

void solve(){
    int n, m;
    cin >> n >> m;

    vector<ll> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    vector<ll> sum(n + 1);
    for(int i = 1; i <= m; ++i){
        ll r, w;
        cin >> r >> w;
        sum[0] -= w;
        sum[r + 1] += w;
    }

    for(int i = 1; i <= n; ++i){
        sum[i] += sum[i - 1];
    }
    for(int i = 1; i <= n; ++i){
        sum[i] += a[i];
    }

    set<pair<ll, ll>> s_sum, s_a;
    for(int i = 1; i <= n; ++i){
        s_sum.insert({sum[i], i});
        s_a.insert({a[i], i});
    }

    int best = s_sum.begin()->second;
    s_sum.erase({sum[best], best});
    s_a.erase({a[best], best});

    ll score = sum[best];
    cout << score << " ";

    ll min_idx = best;
    for(int i = 2; i <= n; ++i){
        auto [min_a, idx] = *s_a.begin();
        s_a.erase(s_a.begin());
        s_sum.erase({sum[idx], idx});
        score += min_a;

        if(idx < min_idx){
            score -= (sum[min_idx] - a[min_idx]);
            score += (sum[idx] - a[idx]);
            min_idx = idx;
        }

        ll curr_score = score;
        if(i != n){
            auto [min_sum, idx2] = *s_sum.begin();
            curr_score = min(curr_score, score + min_sum - (sum[min_idx] - a[min_idx]) - min_a);
        }

        cout << curr_score << " ";
    }
    cout << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve();
}