Problem B
Triangulation

There are $n$ points placed at equal distances on a circle, numbered from $1$ to $n$ in clockwise direction starting from a certain point. Let $d$ be the length of arc between two neighboring points.

BaoBao draws $(2n - 3)$ chords on the circle, each connecting two of the $n$ points. It’s guaranteed that no two chords connect the same pair of points, and no two chords intersect inside the circle (excluding the border). It’s easy to see that, these chords form $(n - 2)$ triangles. These triangles are called a triangulation of the circle.

BaoBao likes the triangulation a lot, so he records the $(n - 2)$ triangles on a piece of paper. The $i$-th triangle is recorded as three integers $k_{i, 1}, k_{i, 2}, k_{i, 3}$, where $k_{i, j} \times d$ is the length of the shortest arc between the $j$-th vertex and its next vertex on the $i$-th triangle. For $j = 1$ and $j = 2$, its next vertex is the $(j + 1)$-th vertex. For $j = 3$, its next vertex is the $1$-st vertex.

Several days later, when BaoBao wants to admire the triangulation again, he finds with dismay that all chords are erased by his roommate DreamGrid, so he has to recover the triangulation according to the paper. Your task is to help BaoBao determine $v_{i, j}$ for all $1 \le i \le n$ and $1 \le j \le 3$, meaning that the $j$-th vertex of the $i$-th triangle is the $v_{i, j}$-th point on the circle. It is possible that BaoBao recorded the wrong information, in this case you should tell BaoBao that such triangulation does not exist.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($3 \le n \le 2 \times 10^5$), indicating the number of points on the circle.

For the following $(n - 2)$ lines, the $i$-th line contains three integers $k_{i, 1}, k_{i, 2}, k_{i, 3}$ ($1 \le k_{i, j} \le \lfloor \frac{n}{2}\rfloor $), where $k_{i, j} \times d$ is the length of the shortest arc between the $j$-th vertex and its next vertex on the $i$-th triangle.

It’s guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^5$.

Output

For each test case:

• If such triangulation exists, first output Yes in one line. Then output $(n - 2)$ lines, where the $i$-th line contains three integers $v_{i, 1}, v_{i, 2}, v_{i, 3}$ separated by a space, meaning that the $j$-th vertex of the $i$-th triangle is the $v_{i, j}$-th point on the circle. If there are multiple valid answers, you can output any of them.

• If such triangulaton does not exist, just output No in one line.

Note

The first and the third sample test cases are illustrated below.

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

Yes
1 2 3
No
Yes
5 2 3
6 1 5
1 2 5
4 5 3