E. Erdős-Ginzburg-Ziv
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After studying the Erdős–Ginzburg–Ziv theorem, Daniel wants to present its proof to the local Opaquely Constructivist Primes Committee. The final step of the theorem constitutes the following problem:

You're given a prime number $$$p$$$, a sequence of integers $$$x_1,\dots,x_{p-1}$$$ between $$$1$$$ and $$$p-1$$$, and a number $$$g$$$. You have to find a sub-sequence of numbers such that their sum is congruent to $$$g$$$ modulo $$$p$$$.

Daniel presented the committee a proof that such a subset exists, but since all committee members are constructivists, they reject Daniel's proof until he provides a concrete construction for the given $$$x_1,\dots,x_{p-1}$$$. "Okay, for which $$$g$$$?" – asked Daniel. "All of them, of course!" – replied the committee.

Since $$$p$$$ may be quite large, Daniel decided to settle on the following construction pattern: He makes a rooted tree of $$$p$$$ vertices numbered $$$0$$$ through $$$p-1$$$, rooted at $$$0$$$. Then, Daniel will use each of the numbers $$$x_1,\dots,x_{p-1}$$$ exactly once to mark each tree edge with a number in such a way that the sum of the numbers on the path from any vertex $$$g$$$ to the root is congruent to $$$g$$$ modulo $$$p$$$.

Since Daniel is not a constructivist, he again only managed to prove that such a tree always exists, but has no idea how to actually construct it. Of course, someone still has to do so to appease the strict committee, and this someone just so happens to be you. Help Daniel!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single prime integer $$$p$$$ ($$$2 \leq p \leq 10^6$$$).

The next line contains the $$$p-1$$$ integers $$$x_i$$$ ($$$1 \leq x_i \leq p-1)$$$.

It is guaranteed that the sum of $$$p$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print $$$p-1$$$ lines.

In the $$$i$$$-th line, print three integers $$$a$$$, $$$b$$$ and $$$x$$$, meaning that there is an edge between vertices $$$a$$$ and $$$b$$$ marked with the number $$$x$$$. Each of $$$x_i$$$ should be used exactly once in the tree description.

Example
Input
3
7
4 2 2 6 4 5
5
1 1 1 1
3
2 2
Output
0 4 4
4 6 2
6 1 2
6 5 6
5 2 4
5 3 5
0 1 1
1 2 1
2 3 1
3 4 1
0 2 2
2 1 2
Note

A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.