Chiaki has a special machine which can generate permutations. You can give any restrictions to the machine, it will generate all the permutation under the restrictions .
Chiaki has generated n restrictions and the i-th of them is that the position of a_i should be less than the position of b_i and c_i.
The restrictions generated by Chiaki are somewhat special and the sequence a₁,a₂,...,a_n, b₁,b₂,...,b_n, c₁, c₂, ..., c_n is a permutation of 1,2,...,3n.
Among all the permutations generated by the machine, Chiaki would like to find one with minimum value.
The value of a permutation p₁,p₂,...,p_n is .

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 105) -- the number of restrictions.
Each of the next n lines contains three integers ai, bi and ci (1 ≤ ai, bi, ci ≤ 3n) denoting a restriction.
It is guaranteed that the sum of all n does not exceed 106.

For each test case, output 3n integers denoting the permutation with minimum value. If there are multiple solutions, you can output any of them.

2
1
1 2 3
2
3 4 2
1 6 5

1 2 3 
3 2 1 4 5 6