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