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$) が含まれ、テストケースの数を表します。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、2つの整数 $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