#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); ++i) {
        os << v[i];
        if (i < (int)v.size() - 1) os << " ";
    }
    return os;
}

class BitVector {
   public:
    BitVector() = default;
    explicit BitVector(const std::vector<bool>& v) {
        const int n = v.size() / sz + 1;
        data.resize(n);
        sum.resize(n + 1);
        for (int i = 0; i < (int)v.size(); ++i)
            data[i / sz] |= v[i] << (i % sz);
        for (int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + __builtin_popcount(data[i]);
    }

    bool operator[](int k) const { return data[k / sz] >> (k % sz) & 1; }

    int rank(int k, bool b) const {
        int mask = (1U << (k % sz)) - 1;
        int r = sum[k / sz] + __builtin_popcount(data[k / sz] & mask);
        return b ? r : k - r;
    }

    int select(int k, bool b) const {
        int lb = 0, ub = data.size();
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (rank(m, b) <= k)
                lb = m;
            else
                ub = m;
        }
        return lb;
    }

   private:
    static constexpr int sz = 32;

    std::vector<uint32_t> data;
    std::vector<int> sum;
};

template <typename T, int MAX_LOG>
class WaveletMatrix {
   public:
    WaveletMatrix() = default;
    explicit WaveletMatrix(std::vector<T> v) : mat(MAX_LOG), cnt0(MAX_LOG) {
        const int n = v.size();
        for (int d = MAX_LOG - 1; d >= 0; --d) {
            std::vector<bool> bit(n);
            for (int i = 0; i < n; ++i) bit[i] = v[i] >> d & 1;
            mat[d] = BitVector(bit);
            std::vector<int> cnt(2);
            for (int i = 0; i < n; ++i) {
                if (!bit[i]) cnt[0]++;
            }
            cnt0[d] = cnt[0];
            cnt[1] = n;
            std::vector<T> nv(n);
            for (int i = n - 1; i >= 0; --i) {
                nv[--cnt[bit[i]]] = v[i];
            }
            v.swap(nv);
        }
        for (int i = 0; i < n; ++i) {
            if (!start.count(v[i])) start[v[i]] = i;
        }
    }

    T operator[](int k) const {
        T ret = 0;
        for (int d = mat.size() - 1; d >= 0; --d) {
            bool b = mat[d][k];
            ret |= T(b) << d;
            k = cnt0[d] * b + mat[d].rank(k, b);
        }
        return ret;
    }

    int rank(int k, T x) const {
        for (int d = mat.size() - 1; d >= 0; --d) {
            bool b = x >> d & 1;
            k = cnt0[d] * b + mat[d].rank(k, b);
        }
        if (start.count(x)) return k - start.at(x);
        return k;
    }

    int range_freq(int l, int r, T ub) const {
        if (l >= r) return 0;
        int ret = 0;
        for (int d = mat.size() - 1; d >= 0; --d) {
            bool b = ub >> d & 1;
            if (b) ret += mat[d].rank(r, 0) - mat[d].rank(l, 0);
            l = cnt0[d] * b + mat[d].rank(l, b);
            r = cnt0[d] * b + mat[d].rank(r, b);
        }
        return ret;
    }

    int range_freq(int l, int r, T lb, T ub) const {
        if (lb >= ub) return 0;
        return range_freq(l, r, ub) - range_freq(l, r, lb);
    }

    int select(int k, T x) const {
        k += start.at(x);
        for (int d = 0; d < (int)mat.size(); ++d) {
            bool b = x >> d & 1;
            k = mat[d].select(k - cnt0[d] * b, b);
        }
        return k;
    }

    T quantile(int l, int r, int k) const {
        T ret = 0;
        for (int d = (int)mat.size() - 1; d >= 0; --d) {
            int cnt = mat[d].rank(r, 0) - mat[d].rank(l, 0);
            bool b = k < cnt ? 0 : 1;
            l = cnt0[d] * b + mat[d].rank(l, b);
            r = cnt0[d] * b + mat[d].rank(r, b);
            if (b) {
                ret |= T(1) << d;
                k -= cnt;
            }
        }
        return ret;
    }

   private:
    std::vector<BitVector> mat;
    std::vector<int> cnt0;
    std::unordered_map<T, int> start;
};

template <typename M>
class PersistentSegmentTree {
    using T = typename M::T;

   public:
    PersistentSegmentTree() = default;
    explicit PersistentSegmentTree(int n)
        : PersistentSegmentTree(std::vector<T>(n, M::id())) {}
    explicit PersistentSegmentTree(const std::vector<T>& v)
        : root(std::make_shared<Node>()) {
        size = 1;
        while (size < (int)v.size()) size <<= 1;
        build(v, root, 0, size);
    }

    T operator[](int k) const { return fold(k, k + 1); }

    PersistentSegmentTree update(int k, const T& x) const {
        return PersistentSegmentTree(update(k, x, root, 0, size), size);
    }

    T fold(int l, int r) const { return fold(l, r, root, 0, size); }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr left, right;
        Node() : val(M::id()), left(nullptr), right(nullptr) {}
        Node(const T& val, const node_ptr& left, const node_ptr& right)
            : val(val), left(left), right(right) {}
    };

    node_ptr root;
    int size;

    PersistentSegmentTree(const node_ptr& root, int size)
        : root(root), size(size) {}

    void build(const std::vector<T>& v, const node_ptr& n, int l, int r) const {
        if (r - l == 1) {
            n->val = l < (int)v.size() ? v[l] : M::id();
            return;
        }
        int m = (l + r) / 2;
        n->left = std::make_shared<Node>();
        build(v, n->left, l, m);
        n->right = std::make_shared<Node>();
        build(v, n->right, m, r);
        n->val = M::op(n->left->val, n->right->val);
    }

    node_ptr update(int k, const T& x, const node_ptr& n, int l, int r) const {
        if (r - l == 1) {
            return std::make_shared<Node>(x, nullptr, nullptr);
        }
        int m = (l + r) / 2;
        if (k < m) {
            auto left = update(k, x, n->left, l, m);
            T val = M::op(left->val, n->right->val);
            return std::make_shared<Node>(val, left, n->right);
        } else {
            auto right = update(k, x, n->right, m, r);
            T val = M::op(n->left->val, right->val);
            return std::make_shared<Node>(val, n->left, right);
        }
    }

    T fold(int a, int b, const node_ptr& n, int l, int r) const {
        if (r <= a || b <= l) return M::id();
        if (a <= l && r <= b) return n->val;
        int m = (l + r) / 2;
        return M::op(fold(a, b, n->left, l, m), fold(a, b, n->right, m, r));
    }
};

struct AddMonoid {
    using T = ll;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

template <typename T>
class Compress {
   public:
    Compress() = default;
    explicit Compress(const std::vector<T>& vs) : xs(vs) {
        std::sort(xs.begin(), xs.end());
        xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    }

    int compress(const T& x) const {
        return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    }

    std::vector<int> compress(const std::vector<T>& vs) const {
        std::vector<int> ret;
        std::transform(vs.begin(), vs.end(), std::back_inserter(ret),
                       [&](const T& x) { return compress(x); });
        return ret;
    }

    T decompress(int i) const { return xs[i]; }

    int size() const { return xs.size(); }

   private:
    std::vector<T> xs;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (auto& x : a) cin >> x;
        vector<ll> b(n);
        rep(_, 0, m) {
            int r, w;
            cin >> r >> w;
            --r;
            b[r] += w;
        }
        revrep(i, n - 1, 0) { b[i] += b[i + 1]; }
        rep(i, 0, n) { b[i] = a[i] - b[i]; }

        vector<ll> ans(n + 1, 1e18);

        Compress<int> comp(a);
        auto ca = comp.compress(a);

        vector<PersistentSegmentTree<AddMonoid>> st(n);
        st[n - 1] = PersistentSegmentTree<AddMonoid>(comp.size());
        st[n - 1] = st[n - 1].update(ca[n - 1], a[n - 1]);
        revrep(i, n - 1, 0) {
            st[i] = st[i + 1].update(ca[i], st[i + 1][ca[i]] + a[i]);
        }

        WaveletMatrix<int, 32> wm(a);

        auto sum_top_k = [&](int l, int k) -> ll {
            if (l == n) return 0;
            int x = wm.quantile(l, n, k - 1);
            ll s = st[l].fold(0, comp.compress(x) + 1);
            int cnt = wm.range_freq(l, n, x + 1);
            s -= 1LL * (cnt - k) * x;
            return s;
        };

        auto solve = [&](auto& solve, int kmin, int kmax, int l, int r) {
            if (kmin > kmax) return;
            int k = (kmin + kmax) / 2;
            pair<ll, int> res(1e18, -1);
            revrep(i, r + 1, l) {
                if (n - i >= k) {
                    ll s = b[i] + sum_top_k(i + 1, k - 1);
                    chmin(res, {s, i});
                }
            }
            auto [s, i] = res;
            ans[k] = s;
            solve(solve, kmin, k - 1, i, r);
            solve(solve, k + 1, kmax, l, i);
        };

        solve(solve, 1, n, 0, n - 1);

        rep(k, 1, n + 1) cout << ans[k] << (k < n ? " " : "\n");
    }
}