#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;

// 定义无限大的初始值
const long long INF = 1e18;
const int N=2e5+50;
// 段树节点结构
struct SegmentTreeNode {
    int left, right;       // 区间范围
    long long minVal;      // 区间最小值
    int minIdx;            // 区间最小值的索引
    long long lazy;        // 懒标记

    SegmentTreeNode() : left(0), right(0), minVal(INF), minIdx(-1), lazy(0) {}
};

// 段树类
class SegmentTree {
private:
    int n; // 数组大小
    vector<SegmentTreeNode> tree;
    vector<long long> arr; // 初始数组

    // 建立段树
    void build(int node, int l, int r) {
        tree[node].left = l;
        tree[node].right = r;
        tree[node].lazy = 0;
        if (l == r) {
            tree[node].minVal = arr[l];
            tree[node].minIdx = l;
            return;
        }
        int mid = (l + r) / 2;
        build(node*2, l, mid);
        build(node*2+1, mid+1, r);
        // 合并子节点的最小值和对应的索引
        if (tree[node*2].minVal < tree[node*2+1].minVal) {
            tree[node].minVal = tree[node*2].minVal;
            tree[node].minIdx = tree[node*2].minIdx;
        }
        else if (tree[node*2].minVal > tree[node*2+1].minVal) {
            tree[node].minVal = tree[node*2+1].minVal;
            tree[node].minIdx = tree[node*2+1].minIdx;
        }
        else { // 相等时取较小的索引
            tree[node].minVal = tree[node*2].minVal;
            tree[node].minIdx = min(tree[node*2].minIdx, tree[node*2+1].minIdx);
        }
    }

    // 传递懒标记
    void pushDown(int node) {
        if (tree[node].lazy != 0) {
            long long lazyVal = tree[node].lazy;
            // 更新左子节点
            tree[node*2].minVal += lazyVal;
            tree[node*2].lazy += lazyVal;
            // 更新右子节点
            tree[node*2+1].minVal += lazyVal;
            tree[node*2+1].lazy += lazyVal;
            // 清除当前节点的懒标记
            tree[node].lazy = 0;
        }
    }

    // 区间更新，加val到[l, r]
    void updateRange(int node, int l, int r, long long val) {
        if (tree[node].right < l || tree[node].left > r) return; // 无交集
        if (tree[node].left >= l && tree[node].right <= r) { // 完全覆盖
            tree[node].minVal += val;
            tree[node].lazy += val;
            return;
        }
        // 部分覆盖，先下传懒标记
        pushDown(node);
        // 更新左右子节点
        updateRange(node*2, l, r, val);
        updateRange(node*2+1, l, r, val);
        // 更新当前节点的最小值和最小值索引
        if (tree[node*2].minVal < tree[node*2+1].minVal) {
            tree[node].minVal = tree[node*2].minVal;
            tree[node].minIdx = tree[node*2].minIdx;
        }
        else if (tree[node*2].minVal > tree[node*2+1].minVal) {
            tree[node].minVal = tree[node*2+1].minVal;
            tree[node].minIdx = tree[node*2+1].minIdx;
        }
        else { // 相等时取较小的索引
            tree[node].minVal = tree[node*2].minVal;
            tree[node].minIdx = min(tree[node*2].minIdx, tree[node*2+1].minIdx);
        }
    }

public:
    SegmentTree(vector<long long> &inputArr) {
        arr = inputArr;
        n = arr.size() - 1;
        tree.resize(4*n + 4);
        build(1, 1, n);
    }

    void addRange(int l, int r, long long val) {
        updateRange(1, l, r, val);
    }

    void subRange(int l, int r, long long val) {
        updateRange(1, l, r, -val);
    }

    pair<long long, int> getGlobalMin() {
        return {tree[1].minVal, tree[1].minIdx};
    }
};
array<int,2> cp[N]; 
signed main(){
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    int tt;
    cin>>tt;
    while(tt--) {
        int n,m,x;
        cin>>n>>m;
        vector<long long> arr;
        arr.push_back(0);
        for (int i = 0; i < n; ++i) {
            cin>>x;
            arr.push_back(x);
        }
        SegmentTree segTree(arr);
        for (int i = 1; i <= m; ++i) {
            cin>>cp[i][0]>>cp[i][1];
            segTree.subRange(1,cp[i][0],cp[i][1]);
        }
        sort(cp+1,cp+m+1,[](array<int,2> a,array<int,2> b) {
            return a[0]<b[0];
        });
        int ans=0;
        for (int i = 1; i <= n; ++i) {
            auto [val,pos] = segTree.getGlobalMin();
            ans+=val;
            cout<<ans<<' ';
            segTree.addRange(pos,pos,1e18-val);
            int l=0,r=m+1;
            while(r-l>1) {
                int M=(l+r)>>1;
                if(cp[M][0]<pos) l=M;
                else r=M;
            }
            for (int j = l+1; j <= m; ++j) {
                segTree.addRange(1,cp[j][0],cp[j][1]);
            }
            m=l;
        }
        cout<<endl;
    }
    return 0;
}