Асхат — начинающий бизнесмен. Он быстро понял, что программирование — невыгодное дело, поэтому решил открыть ферму по разведению кур.

На его ферме есть $n$ кур, выстроенных в ряд. $i$-я курица может съесть не более $a_i$ зерен. Также есть $m$ кормушек, каждая из которых описывается целыми числами $l_j, r_j, c_j$. $j$-я кормушка может кормить $i$-ю курицу, если $l_j \le i \le r_j$, и в этой кормушке содержится $c_j$ зерен.

Оказывается, у любого бизнеса есть свои подводные камни, в данном случае это контроль кормления кур, представленный Ильдаром. Он утверждает, что на каждой уважающей себя куриной ферме должен быть представитель кур. Это означает, что должен существовать такой номер курицы $i$, что для каждой кормушки $j$ выполняется условие $l_j \le i \le r_j$. Все кормушки, которые не подчиняются этому правилу, должны быть уничтожены.

Теперь Асхат просит вас найти для каждого $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