You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

你有一块反重力的巨大磁铁。

题目描述

你有 $n$ 种铁钉和 $m$ 个磁铁。第 $i$ 种铁钉有 $a_i$ 个，只能被编号在 $[l_i, r_i]$ 内的磁铁吸引。为了不让磁铁消失磁力，第 $i$ 个磁铁最多只能吸引 $c_i$ 个铁钉。

但是你有一个反重力引擎。具体地，假设你把引擎安装在了磁铁 $k$ 处（反重力引擎不会让 $c_k$ 减少），那么一种原先被 $[L, R]$ 内磁铁吸引的铁钉可以被 $[\min(L, k), \max(R, k)]$ 内的所有磁铁吸引。

因为你不想让铁钉把你的仓库堆满，你想知道对于所有 $k$ 取 $1 \sim n$ 的值，最多能有多少枚铁钉被吸引。

输入格式

本题有多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 第一行两个整数 $m, n$。
• 接下来一行 $m$ 个整数 $c_1\dots c_m$。
• 接下来 $n$ 行，每行三个整数 $l_i, r_i, a_i$。

输出格式

对于每组数据，一行 $m$ 个整数，分别表示 $k$ 取 $1 \sim m$ 的答案。

样例

2
4 3
3 3 2 2
1 2 2
3 3 3
2 2 4
5 1
1 2 3 4 5
1 1 17

8 7 7 9
1 3 6 10 15

数据规模与约定

本题采用子任务捆绑测试，可能轻微卡常（但是保证开了 $2.5$ 倍时限以上）。

• Subtask 0（25 pts）：$\sum n \leq 80$，$\sum m \leq 80$。
• Subtask 1（15 pts）：$\sum n \leq 500$，$\sum m \leq 500$。
• Subtask 2（10 pts）：$\sum n \leq 10^4$，$\sum m \leq 80$。
• Subtask 3（50 pts）：无特殊限制。

对于 Subtask 0~2 时间限制为 $1$ 秒，Subtask 3 时间限制为 $5$ 秒。

对于 $100\%$ 的数据，保证 $1 \leq \sum n, \sum m \leq 10^5$，$1 \leq a_i, b_i \leq 10^9$，$1 \leq l_i \leq r_i \leq n$。