You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($3 \le n \le 10^6$, $1 \le m \le 4 \cdot 10^5$) — denoting the graph have $n$ vertices and $3m$ edges.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^6$) — the initial weights of each vertex.

Then $m$ lines follows. The $i$-th line contains three integers $a_i$, $b_i$, $c_i$ ($1 \leq a_i < b_i < c_i \leq n$) — denotes that three edges $(a_i,b_i)$, $(b_i,c_i)$ and $(c_i,a_i)$.

Note that the graph may contain multi-edges: a pair $(x,y)$ may appear in multiple triangles.

It is guaranteed that the sum of $n$ over all test cases do not exceed $10^6$ and the sum of $m$ over all test cases do not exceed $4 \cdot 10^5$.

Output

For each test case, output $m$ lines of $3$ integers each.

The $i$-th line should contains three integers $e_{ab},e_{bc},e_{ca}$ ($1 \leq e_{ab}, e_{bc} , e_{ca} \leq 4$), denoting the choice of value $x$ for edges $(a_i, b_i)$, $(b_i,c_i)$ and $(c_i, a_i)$ respectively.

4
4 1
0 0 0 0
1 2 3
5 2
0 0 0 0 0
1 2 3
1 4 5
4 4
3 4 5 6
1 2 3
1 2 4
1 3 4
2 3 4
5 4
0 1000000 412 412 412
1 2 3
1 4 5
2 4 5
3 4 5

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

Note

In the first test case, the initial weights are $[0,0,0,0]$. We have added values as follows:

• Added $2$ to vertices $1$ and $2$
• Added $1$ to vertices $1$ and $3$
• Added $3$ to vertices $2$ and $3$

The final weights are $[3,5,4,0]$. The output is valid because $a_1 \neq a_2$, $a_1 \neq a_3$, $a_2 \neq a_3$, and that all chosen values are between $1$ and $4$.

In the second test case, the initial weights are $[0,0,0,0,0]$. The weights after the operations are $[12,5,6,7,6]$. The output is valid because $a_1 \neq a_2$, $a_1 \neq a_3$, $a_2 \neq a_3$, and that $a_1 \neq a_4$, $a_1 \neq a_5$, $a_4 \neq a_5$, and that all chosen values are between $1$ and $4$.

In the third test case, the initial weights are $[3,4,5,6]$. The weights after the operations are $[19,16,17,20]$, so all final weights are distinct, which means no two adjacent vertices have the same weight.