考虑 $t_i = 0$ 怎么做。

显然的二分图模型，左部点为机器人，右部点为容器，源点向左部点 $i$ 连容量为 $c_i$ 的边，右部点 $i$ 向汇点连容量为 $a_i$ 的边，若 $j \in [l_i, r_i]$ 就从左部点 $i$ 向右部点 $j$ 连容量为 $+\infty$ 的边。最大流即为答案。

考虑 Hall 定理，最大流即为 $\sum\limits_{i = 1}^m c_i - \max\limits_S \{\sum\limits_{i \in S} c_i - \sum\limits_{i \in N(S)} a_i\}$，其中 $N(S)$ 为被 $S$ 中区间包含的容器的集合。考虑求 $\max\limits_S \{\sum\limits_{i \in S} c_i - \sum\limits_{i \in N(S)} a_i\}$。枚举 $T = N(S)$，为了最大化 $\sum\limits_{i \in S} c_i$ 肯定是把所有的区间内点都被 $T$ 包含的机器人选上。设 $N(T)$ 为区间内的点都被 $T$ 包含的机器人集合，那么上述式子等于 $\max\limits_T \{\sum\limits_{i \in N(T)} c_i - \sum\limits_{i \in T} a_i\}$。

现在问题变为，选若干个不交区间使得其权值和最大。首先将 $a$ 变为其前缀和数组。一个区间 $[l, r]$ 的权值 $w(l, r)$ 为所有被 $[l, r]$ 包含的区间的权值和减去 $a_r - a_{l - 1}$。考虑 DP，设 $f_i$ 为前缀 $[1, i]$ 的答案，有 $f_i = \max(f_{i - 1}, \max\limits_{j = 1}^i f_{j - 1} + w(j, i))$。其中 $\max$ 的后半部分可以线段树维护。所以我们可以在 $O(n \log n)$ 的时间内解决 $t_i = 0$。

考虑原题，对于单个 $x$，显然全部 $t_i = 1$ 的区间都包含它。对于全部 $t_i = 0$ 的区间预处理出前缀和后缀的 DP 数组 $f, g$。若 $x \notin T$，答案即为 $f_{i - 1} + g_{i + 1}$；若 $x \in T$，考虑枚举 $T$ 中包含 $x$ 的极长区间 $[l, r]$，仍然定义一个区间 $[l, r]$ 的权值 $w(l, r)$ 为所有被 $[l, r]$ 包含的区间的权值和减去 $a_r - a_{l - 1}$，那么答案即为 $\max\limits_{l = 1}^x \max\limits_{r = x}^n f_{l - 1} + g_{r + 1} + w(l, r)$。容易发现它能被刻画成若干个矩形加、若干个 $[1, x], [x, n]$ 的矩形 $\max$，扫描线 + 线段树维护区间历史最值即可。

时间复杂度 $O((n + m) \log n)$。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, m, a[maxn];
struct node {
	ll l, r, v, t;
} b[maxn], c[maxn];

namespace SGT {
	ll a[maxn << 2], tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = max(a[x << 1], a[x << 1 | 1]);
	}
	
	inline void pushtag(int x, ll y) {
		a[x] += y;
		tag[x] += y;
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		pushtag(x << 1, tag[x]);
		pushtag(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		tag[rt] = 0;
		if (l == r) {
			a[rt] = -1e18;
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushtag(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void modify(int rt, int l, int r, int x, ll y) {
		if (l == r) {
			a[rt] = y;
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		(x <= mid) ? modify(rt << 1, l, mid, x, y) : modify(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	ll query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return a[rt];
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		ll res = -1e18;
		if (ql <= mid) {
			res = max(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = max(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
}

vector<pii> vc[maxn];
ll f[maxn], g[maxn];

struct mat {
	ll a[2][2];
	mat() {
		mems(a, -0x3f);
	}
} I;

inline mat operator + (const mat &a, const mat &b) {
	mat res;
	res.a[0][0] = max(a.a[0][0], b.a[0][0]);
	res.a[0][1] = max(a.a[0][1], b.a[0][1]);
	res.a[1][0] = max(a.a[1][0], b.a[1][0]);
	res.a[1][1] = max(a.a[1][1], b.a[1][1]);
	return res;
}

inline mat operator * (const mat &a, const mat &b) {
	mat res;
	res.a[0][0] = max(res.a[0][0], a.a[0][0] + b.a[0][0]);
	res.a[0][1] = max(res.a[0][1], a.a[0][0] + b.a[0][1]);
	res.a[1][0] = max(res.a[1][0], a.a[1][0] + b.a[0][0]);
	res.a[1][1] = max(res.a[1][1], a.a[1][0] + b.a[0][1]);
	res.a[0][0] = max(res.a[0][0], a.a[0][1] + b.a[1][0]);
	res.a[0][1] = max(res.a[0][1], a.a[0][1] + b.a[1][1]);
	res.a[1][0] = max(res.a[1][0], a.a[1][1] + b.a[1][0]);
	res.a[1][1] = max(res.a[1][1], a.a[1][1] + b.a[1][1]);
	return res;
}

namespace ST {
	mat a[maxn << 2], tag[maxn << 2];
	bool vis[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = a[x << 1] + a[x << 1 | 1];
	}
	
	inline void pushtag(int x, mat y) {
		a[x] = a[x] * y;
		tag[x] = tag[x] * y;
		vis[x] = 1;
	}
	
	inline void pushdown(int x) {
		if (!vis[x]) {
			return;
		}
		pushtag(x << 1, tag[x]);
		pushtag(x << 1 | 1, tag[x]);
		tag[x] = I;
		vis[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		tag[rt] = I;
		vis[rt] = 0;
		if (l == r) {
			a[rt].a[0][0] = a[rt].a[0][1] = a[rt].a[1][0] = a[rt].a[1][1] = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, mat x) {
		if (ql <= l && r <= qr) {
			pushtag(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	ll query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return max(a[rt].a[0][0], a[rt].a[0][1]);
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		ll res = 0;
		if (ql <= mid) {
			res = max(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = max(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
}

struct line {
	ll l, r, x;
	line(ll a = 0, ll b = 0, ll c = 0) : l(a), r(b), x(c) {}
};

vector<line> md[maxn];

inline void add(int xl, int xr, int yl, int yr, ll x) {
	md[xl].pb(yl, yr, x);
	md[xr + 1].pb(yl, yr, -x);
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		a[i] += a[i - 1];
		vector<pii>().swap(vc[i]);
		vector<line>().swap(md[i]);
	}
	ll s = 0;
	for (int i = 1; i <= m; ++i) {
		scanf("%lld%lld%lld%lld", &b[i].l, &b[i].r, &b[i].v, &b[i].t);
		s += b[i].v;
		if (!b[i].t) {
			vc[b[i].r].pb(b[i].l, b[i].v);
		}
	}
	SGT::build(1, 0, n);
	f[0] = 0;
	SGT::modify(1, 0, n, 0, 0);
	for (int i = 1; i <= n; ++i) {
		for (pii p : vc[i]) {
			SGT::update(1, 0, n, 0, p.fst - 1, p.scd);
		}
		f[i] = max(f[i - 1], SGT::query(1, 0, n, 0, i - 1) - a[i]);
		SGT::modify(1, 0, n, i, f[i] + a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		vector<pii>().swap(vc[i]);
	}
	for (int i = 1; i <= m; ++i) {
		if (!b[i].t) {
			vc[b[i].l].pb(b[i].r, b[i].v);
		}
	}
	SGT::build(1, 1, n + 1);
	g[n + 1] = 0;
	SGT::modify(1, 1, n + 1, n + 1, -a[n]);
	for (int i = n; i; --i) {
		for (pii p : vc[i]) {
			SGT::update(1, 1, n + 1, p.fst + 1, n + 1, p.scd);
		}
		g[i] = max(g[i + 1], SGT::query(1, 1, n + 1, i + 1, n + 1) + a[i - 1]);
		SGT::modify(1, 1, n + 1, i, g[i] - a[i - 1]);
	}
	ST::build(1, 1, n);
	for (int i = 1; i <= n + 1; ++i) {
		if (i < n) {
			add(i + 1, i + 1, i + 1, n, f[i] + a[i]);
		}
		if (i > 1) {
			add(1, i - 1, i - 1, i - 1, g[i] - a[i - 1]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		add(1, b[i].l, b[i].r, n, b[i].v);
	}
	for (int i = 1; i <= n; ++i) {
		sort(md[i].begin(), md[i].end(), [&](const line &a, const line &b) {
			return a.x < b.x;
		});
		for (line u : md[i]) {
			mat x;
			x.a[0][0] = x.a[1][0] = 0;
			x.a[0][1] = -inf;
			x.a[1][1] = u.x;
			ST::update(1, 1, n, u.l, u.r, x);
		}
		printf("%lld%c", s - max(f[i - 1] + g[i + 1], ST::query(1, 1, n, i, n)), " \n"[i == n]);
	}
}

int main() {
	I.a[0][0] = I.a[1][1] = 0;
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}