Gellyfish 有一个 $$$n$$$ 整数数组 $$$c_1, c_2, \ldots, c_n$$$。一开始,$$$c = [a_1, a_2, \ldots, a_n]$$$。
Gellyfish 将对 $$$c$$$ 进行 $$$q$$$ 修改。
对于 $$$i = 1,2,\ldots,q$$$,Gellyfish 被赋予 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$ 之间的三个整数 $$$1$$$ 和 $$$n$$$ 之间。然后 Gellyfish 将设置 $$$c_{z_i} := \min(c_{x_i}, c_{y_i})$$$。
$$$q$$$ 修改后,$$$c = [b_1, b_2, \ldots, b_n]$$$。
现在 Flower 知道 $$$b$$$ 的值以及所有 $$$1 \leq i \leq q$$$ 的整数 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$ 的值,但她不知道 $$$a$$$ 的值。
Flower 想要找到数组 $$$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$$$) — 修改 $$$q$$$ 后数组 $$$c$$$ 的值。
以下 $$$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”。
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
32 11 22 1 23 21 2 32 3 21 2 16 41 2 2 3 4 55 6 64 5 53 4 42 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$$$在给定的修改后从$$$a$$$变为$$$b$$$,并且$$$c$$$在每次修改时都没有改变。