题目描述

Askhat 原本打算靠写程序创业，后来很快发现这门生意并不赚钱，于是转身开了一座养鸡场。

养鸡场里有 $n$ 只鸡排成一行，第 $i$ 只鸡最多能吃 $a_i$ 粒饲料。场里还有 $m$ 个饲料器，第 $j$ 个饲料器由三个整数 $l_j,r_j,c_j$ 描述：它能给所有满足 $l_j\le i\le r_j$ 的鸡喂食，并且这个饲料器中共有 $c_j$ 粒饲料。

养鸡场的监管员 Ildar 提出了一条奇怪的规定：一家体面的养鸡场必须选出一只“代表鸡”。也就是说，所有保留下来的饲料器都必须能够给这只代表鸡喂食。若某个饲料器不满足这条规定，就必须被移除。

现在 Askhat 想知道：如果把第 $i$ 只鸡选为代表鸡，只保留所有满足 $l_j\le i\le r_j$ 的饲料器，那么最多一共能给所有鸡喂多少粒饲料？

喂食时，每个饲料器中的饲料可以分配给它能喂到的鸡；每个饲料器最多分配 $c_j$ 粒，每只鸡最多吃 $a_i$ 粒。

请对每个 $i$ 求出答案。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来依次给出每组测试数据。

每组测试数据第一行包含两个整数 $n,m$，分别表示鸡的数量和饲料器数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行包含三个整数 $l_j,r_j,c_j$，描述一个饲料器。

保证所有测试数据中 $n$ 的总和不超过 $10^5$，$m$ 的总和也不超过 $10^5$。

输出格式

对于每组测试数据，输出一行 $n$ 个整数，第 $i$ 个整数表示选择第 $i$ 只鸡作为代表鸡时的答案。

数据范围

• $1\le t\le 10^4$；
• $1\le n,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\le 10^5$；
• 所有测试数据中 $\sum m\le 10^5$。

样例 1

输入

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

输出

2 5 2 0