Askhat 是一位有前途的商人。他很快发现编程是一项无利可图的生意，于是决定开一家养鸡场。

他的养鸡场里有 $n$ 只排成一行的鸡。第 $i$ 只鸡最多能吃 $a_i$ 粒谷物。场里有 $m$ 个喂食器，每个喂食器由整数 $l_j, r_j, c_j$ 描述。如果 $l_j \le i \le r_j$，则第 $j$ 个喂食器可以喂第 $i$ 只鸡，且该喂食器内有 $c_j$ 粒谷物。

事实证明，任何生意都有其陷阱，这次的陷阱是鸡饲料控制，由 Ildar 负责。他声称，每个体面的养鸡场都必须有一只“鸡代表”。也就是说，必须存在一只鸡 $i$，使得对于每一个喂食器 $j$，都有 $l_j \le i \le r_j$ 成立。所有不遵守此规则的喂食器都必须被清除。

现在 Askhat 请你计算，对于每一只鸡 $i$，如果我们只保留那些能够喂养鸡 $i$ 的喂食器，那么鸡 $i$ 最多能被喂食多少粒谷物。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)，分别表示鸡的数量和喂食器的数量。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示鸡能吃的谷物数量。

接下来的 $m$ 行，每行包含三个整数 $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$)，描述第 $j$ 个喂食器。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数，表示问题的答案。

样例

样例输入 1

1
4 3
3 3 2 2
1 2 2
3 3 3
2 2 4

样例输出 1

2 5 2 0