有 $n$ 只鸡站成一排，第 $i$ 只鸡至多能吃 $a_i$ 的谷子。
有 $m$ 个波特，第 $j$ 个波特可以给第 $l_j,l_j+1,\cdots,r_j$ 只鸡喂谷子，并且它只携带了 $c_j$ 的谷子。波特不需要把携带的所有谷子都喂出去，只需要保证喂出去的谷子不超过 $c_j$ 即可。
对于每个 $i$ ，求出如果只保留满足 $l_j\le i\le r_j$ 的波特，那么最多一共能喂多少谷子。
输入格式
每个测试点的第一行是一个正整数 $T$ ，表示数据组数。每组数据的格式如下。
第一行两个正整数 $n,m$ ，分别表示鸡和波特的数量。
第二行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$ ，表示每只鸡能吃的谷子数量。
接下来 $m$ 行，第 $j$ 行三个整数 $l_j,r_j,c_j$ ，描述第 $j$ 个波特。
输出格式
对每组数据输出一行 $n$ 个非负整数，表示答案。
样例
样例输入1
1 4 3 3 3 2 2 1 2 2 3 3 3 2 2 4
样例输出1
2 5 2 0
样例2
见下发文件中的 ex_2.in/ex_2.ans。
数据范围
本题采用子任务捆绑测试。
对于所有数据，保证 $1\le T\le 10^4,1\le \sum n,\sum m\le 10^5,0\le a_i\le 10^9,1\le l_j\le r_j\le n,0\le c_j\le 10^9$ 。
| 子任务编号 | $\sum n,\sum m\le $ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $300$ | $ $ | $15$ |
| $2$ | $2000$ | $ $ | $15$ |
| $3$ | $10^5$ | $l_j=1,r_j\le r_{j+1}$ | $20$ |
| $4$ | $10^5$ | $l_j\le l_{j+1},r_j\le r_{j+1}$ | $25$ |
| $5$ | $10^5$ | $ $ | $25$ |