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$ 的餵食器，那麼雞群總共最多能被餵食多少顆穀物。

輸入格式

第一行包含一個整數 $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