Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
Statistics

有 $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$