B. Гелифиш и камелия японская
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Гелифиша есть массив из $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$. Изначально $$$c = [a_1, a_2, \ldots, a_n]$$$.

Гелифиш сделает $$$q$$$ модификаций массива $$$c$$$.

Для $$$i = 1,2,\ldots,q$$$ Гелифишу даются три целых числа $$$x_i$$$, $$$y_i$$$ и $$$z_i$$$ в диапазоне от $$$1$$$ до $$$n$$$. Затем Гелифиш присваивает $$$c_{z_i} := \min(c_{x_i}, c_{y_i})$$$.

После $$$q$$$ модификаций $$$c = [b_1, b_2, \ldots, b_n]$$$.

Теперь Флауэр знает значение $$$b$$$ и значения целых чисел $$$x_i$$$, $$$y_i$$$ и $$$z_i$$$ для всех $$$1 \leq i \leq q$$$, но она не знает значение $$$a$$$.

Флауэр хочет найти любое возможное значение массива $$$a$$$ или сообщить, что такого $$$a$$$ не существует.

Если существует несколько возможных значений массива $$$a$$$, вы можете вывести любое из них.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 3 \cdot 10^5$$$) — размер массива и количество модификаций.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — значение массива $$$c$$$ после $$$q$$$ модификаций.

Следующие $$$q$$$ строк каждая содержат три целых числа $$$x_i$$$, $$$y_i$$$ и $$$z_i$$$ ($$$1 \leq x_i, y_i, z_i \leq n$$$) — описание $$$i$$$-й модификации.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если искомое $$$a$$$ существует, выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) на отдельной строке. В противном случае выведите «-1» на отдельной строке.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
2 1
1 2
2 1 2
3 2
1 2 3
2 3 2
1 2 1
6 4
1 2 2 3 4 5
5 6 6
4 5 5
3 4 4
2 3 3
Выходные данные
-1
1 2 3 
1 2 3 4 5 5
Примечание

В первом наборе входных данных, основываясь на данной последовательности модификаций, мы знаем, что $$$b_1 = a_1$$$ и $$$b_2 = \min(a_1, a_2)$$$. Поэтому необходимо, чтобы $$$b_2 \leq b_1$$$. Однако для данного $$$b$$$ у нас $$$b_1 \lt b_2$$$. Следовательно, решения не существует.

Во втором наборе входных данных мы можем видеть, что данный $$$c$$$ становится $$$b$$$ из $$$a$$$ после заданных модификаций, и $$$c$$$ не изменяется при каждой модификации.