Askhat est un homme d'affaires en devenir. Il a rapidement compris que la programmation est une activité peu rentable, il a donc décidé d'ouvrir un élevage de poulets.

Sa ferme se compose de $n$ poulets rangés en ligne. Le $i$-ème poulet peut manger au plus $a_i$ grains. Il y a $m$ mangeoires, chacune décrite par des entiers $l_j, r_j, c_j$. La $j$-ème mangeoire peut nourrir le $i$-ème poulet si $l_j \le i \le r_j$, et elle contient $c_j$ grains.

Il s'avère que chaque entreprise a ses pièges, dans ce cas, il s'agit du contrôle de l'alimentation des poulets, représenté par Ildar. Il prétend que chaque élevage de poulets respectable doit avoir un poulet représentant. C'est-à-dire qu'il doit exister un poulet $i$ tel que $l_j \le i \le r_j$ soit vrai pour chaque mangeoire $j$. Toutes les mangeoires qui ne respectent pas cette règle doivent être exterminées.

Maintenant, Askhat vous demande de trouver, pour chaque $i$, quel est le nombre maximum de grains qui peuvent être donnés aux poulets si nous ne gardons que les mangeoires qui peuvent nourrir le poulet $i$.

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 10^4$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n, m$ ($1 \le n, m \le 10^5$) — le nombre de poulets et le nombre de mangeoires respectivement.

La ligne suivante contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — le nombre de grains que les poulets peuvent manger.

Chacune des $m$ lignes suivantes contient trois entiers $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$) — la description de la $j$-ème mangeoire.

Il est garanti que la somme de $n$ et la somme de $m$ pour tous les cas de test n'excèdent pas $10^5$.

Sortie

Pour chaque cas de test, affichez $n$ entiers — la réponse au problème.

Exemples

Entrée 1

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

Sortie 1

2 5 2 0