Askhat は将来有望な実業家です。彼はプログラミングが儲からないビジネスであることにすぐに気づき、養鶏場を開くことにしました。

彼の農場には $n$ 羽の鶏が一列に並んでいます。$i$ 番目の鶏は最大で $a_i$ 粒の穀物を食べることができます。$m$ 個の餌箱があり、それぞれが整数 $l_j, r_j, c_j$ によって記述されます。$j$ 番目の餌箱は $l_j \le i \le r_j$ を満たす $i$ 番目の鶏に餌を与えることができ、その餌箱には $c_j$ 粒の穀物が入っています。

どんなビジネスにも落とし穴があるもので、今回は Ildar という人物による鶏の餌やり管理という形でそれが現れました。彼は、立派な養鶏場には必ず「鶏の代表」が存在しなければならないと主張しています。つまり、すべての餌箱 $j$ に対して $l_j \le i \le r_j$ を満たすような鶏 $i$ が存在しなければなりません。この規則に従わない餌箱はすべて排除されなければなりません。

Askhat はあなたに、各 $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$ 行のそれぞれには、3 つの整数 $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