/*
ulimit -s 1024000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && ulimit -v 128000 && ./%<
ulimit -s 1024000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && ./%<
echo && cat out.out && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endif

const int N = 2e5 + 3;
const llt Inf = 0x3f3f3f3f3f3f3f3fll;
int n, m, _a[N]; llt qa[N], aas[N], df[N], dg[N];
vector<pair<int, int>> pla[N], pra[N], plb[N], prb[N];

#define lson (t << 1)
#define rson (t << 1 | 1)
#define mid ((l + r) >> 1)
class Seg{
private:
	static const int D = N << 2;
	llt nd[D], tg[D]; function<llt(llt, llt)> F;
	void add(llt v, int t){ nd[t] += v, tg[t] += v; }
	void Dwn(int t){ if(llt &x = tg[t]) add(x, lson), add(x, rson), x = 0; }
	void Upd(int t){ nd[t] = F(nd[lson], nd[rson]); }
public:
	Seg(const auto &f) : F(f){}
	void Add(int L, int R, llt v, int l = 1, int r = n, int t = 1){
		if(l == L && r == R) return add(v, t), void();
		Dwn(t);
		if(R <= mid) Add(L, R, v, l, mid, lson);
		else if(L > mid) Add(L, R, v, mid + 1, r, rson);
		else Add(L, mid, v, l, mid, lson), Add(mid + 1, R, v, mid + 1, r, rson);
		Upd(t);
	}
	llt Get(){ return nd[1]; }
	void Clr(){ memset(nd, 0, sizeof nd), memset(tg, 0, sizeof tg); }
	friend void Cdq(int, int, int);
} pre([](llt a, llt b){ return a < b ? a : b; }),
	nxt([](llt a, llt b){ return a > b ? a : b; }),
	seg([](llt a, llt b){ return a < b ? a : b; });

llt tp[N];
void Cdq(int l = 1, int r = n, int t = 1){
	if(l == r){
		llt s = 0; pre.nd[t] = -qa[l - 1] + df[l - 1], nxt.nd[t] = -qa[l] - dg[r + 1];
		for(auto [nr, v] : plb[l]) if(nr == r) pre.add(-v, t), nxt.add(v, t), s += v;
		return aas[l] = max(aas[l], s - qa[l] + qa[l - 1] - df[l - 1] - dg[r + 1]), void();
	}
	Cdq(l, mid, lson), Cdq(mid + 1, r, rson);
	tp[l - 1] = tp[r + 1] = 0;
	for(int nl = mid; nl >= l; --nl){
		for(auto [nr, v] : plb[nl]) if(nr <= r) nxt.Add(max(nr, mid + 1), r, v, mid + 1, r, rson);
		tp[nl] = nxt.nd[rson] + qa[nl - 1] - df[nl - 1];
	}
	for(int nl = l; nl <= mid; ++nl) aas[nl] = max(aas[nl], tp[nl] = max(tp[nl], tp[nl - 1]));
	for(int nr = mid + 1; nr <= r; ++nr){
		for(auto [nl, v] : prb[nr]) if(l <= nl) pre.Add(l, min(mid, nl), -v, l, mid, lson);
		tp[nr] = -qa[nr] - pre.nd[lson] - dg[nr + 1];
	}
	for(int nr = r; nr > mid; --nr) aas[nr] = max(aas[nr], tp[nr] = max(tp[nr], tp[nr + 1]));
	pre.Upd(t), nxt.Upd(t);
}
#undef lson
#undef rson
#undef mid

void Dp(){
	seg.Add(1, n, Inf);
	for(int r = 1; r <= n; ++r){
		seg.Add(r, r, -Inf + df[r - 1]), seg.Add(1, r, _a[r]);
		for(auto [l, v] : pra[r]) seg.Add(1, l, -v);
		df[r] = min(df[r - 1], seg.Get());
	}
	seg.Clr(), seg.Add(1, n, Inf);
	for(int l = n; l; --l){
		seg.Add(l, l, -Inf + dg[l + 1]), seg.Add(l, n, _a[l]);
		for(auto [r, v] : pla[l]) seg.Add(r, n, -v);
		dg[l] = min(dg[l + 1], seg.Get());
	}
}

void Solve(){
	cin >> n >> m;
	llt sb = 0;
	for(int i = 1; i <= n; ++i) cin >> _a[i], qa[i] = qa[i - 1] + _a[i];
	for(int i = 1, l, r, b, t; i <= m; ++i){
		cin >> l >> r >> b >> t;
		if(!t) pla[l].emplace_back(r, b), pra[r].emplace_back(l, b);
		plb[l].emplace_back(r, b), prb[r].emplace_back(l, b), sb += b;
	}
	Dp(), Cdq();
	for(int i = 1; i <= n; ++i) cout << sb - max(aas[i], -df[i] - dg[i + 1]) << ' ';
	cout << endl;
}

void Clear(){
	for(int i = 1; i <= n; ++i) aas[i] = 0, pla[i].clear(), pra[i].clear(), plb[i].clear(), prb[i].clear();
	memset(df, 0, sizeof df), memset(dg, 0, sizeof dg);
	pre.Clr(), nxt.Clr(), seg.Clr();
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tid, t;
	cin >> tid >> t;
	while(t--) Solve(), Clear();
}