Askhat jest początkującym biznesmenem. Szybko zrozumiał, że programowanie to nierentowny biznes, więc postanowił otworzyć fermę kurczaków.

Jego ferma składa się z $n$ kurczaków ustawionych w rzędzie. $i$-ty kurczak może zjeść co najwyżej $a_i$ ziaren. Istnieje $m$ karmników, z których każdy opisany jest liczbami całkowitymi $l_j, r_j, c_j$. $j$-ty karmnik może nakarmić $i$-tego kurczaka, jeśli $l_j \le i \le r_j$, a w karmniku znajduje się $c_j$ ziaren.

Okazuje się, że każdy biznes ma swoje pułapki, w tym przypadku jest to kontrola karmienia kurczaków, reprezentowana przez Ildara. Twierdzi on, że każda szanująca się ferma kurczaków musi mieć kurczaka-reprezentanta. Oznacza to, że musi istnieć taki kurczak $i$, że dla każdego karmnika $j$ zachodzi $l_j \le i \le r_j$. Karmniki, które nie spełniają tego warunku, muszą zostać zlikwidowane.

Teraz Askhat prosi Cię o znalezienie dla każdego $i$ maksymalnej liczby ziaren, które można podać kurczakom, jeśli pozostawimy tylko te karmniki, które mogą nakarmić kurczaka $i$.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę zestawów danych. Następnie następuje opis zestawów danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $n, m$ ($1 \le n, m \le 10^5$) — odpowiednio liczbę kurczaków i liczbę karmników.

Kolejna linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — liczbę ziaren, które mogą zjeść poszczególne kurczaki.

Każda z kolejnych $m$ linii zawiera trzy liczby całkowite $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$) — opis $j$-tego karmnika.

Gwarantuje się, że suma $n$ oraz suma $m$ dla wszystkich zestawów danych nie przekraczają $10^5$.

Wyjście

Dla każdego zestawu danych wypisz $n$ liczb całkowitych — odpowiedź na problem.

Przykład

Wejście 1

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

Wyjście 1

2 5 2 0