B. 水母与山茶花

题目描述

水母有一个包含 $n$ 个整数的数组 $c_1, c_2, \dots, c_n$。初始时，$c = [a_1, a_2, \dots, a_n]$。

水母将对 $c$ 进行 $q$ 次修改操作。

对于第 $i = 1, 2, \dots, q$ 次修改，给定三个介于 $1$ 和 $n$ 之间的整数 $x_i$、$y_i$ 和 $z_i$。然后水母将执行以下赋值：

经过这 $q$ 次修改后，$c = [b_1, b_2, \dots, b_n]$。

现在，Flower 知道 $b$ 的值，也知道所有 $1 \le i \le q$ 对应的 $x_i$、$y_i$ 和 $z_i$，但她不知道 $a$ 的值。

Flower 想要找到任意一个可能的数组 $a$，或者报告不存在这样的 $a$。

如果存在多个可能的数组 $a$，你可以输出其中任意一个。

输入格式

每个测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$）——数组的长度和修改次数。

每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$）——经过 $q$ 次修改后数组 $c$ 的值。

接下来的 $q$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $z_i$（$1 \le x_i, y_i, z_i \le n$）——描述第 $i$ 次修改操作。

保证所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，如果存在数组 $a$，则在一行中输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 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 \le b_1$。然而，对于给定的 $b$，我们有 $b_1 < b_2$。因此，不存在解。

在第二个测试用例中，我们可以看到给定的 $c$ 在经过指定的修改后从 $a$ 变成了 $b$，并且每次修改都没有改变 $c$ 的值。