Tree is a connected graph without cycles. It can be shown that any tree of $$$n$$$ vertices has exactly $$$n - 1$$$ edges.

Leaf is a vertex in the tree with exactly one edge connected to it.

Distance between two vertices $$$u$$$ and $$$v$$$ in a tree is the minimum number of edges that must be passed to come from vertex $$$u$$$ to vertex $$$v$$$.

Alex's birthday is coming up, and Timofey would like to gift him a tree of $$$n$$$ vertices. However, Alex is a very moody boy. Every day for $$$q$$$ days, he will choose an integer, denoted by the integer chosen on the $$$i$$$-th day by $$$d_i$$$. If on the $$$i$$$-th day there are not two leaves in the tree at a distance exactly $$$d_i$$$, Alex will be disappointed.

Timofey decides to gift Alex a designer so that he can change his tree as he wants. Timofey knows that Alex is also lazy (a disaster, not a human being), so at the beginning of every day, he can perform no more than one operation of the following kind:

Choose vertices $$$u$$$, $$$v_1$$$, and $$$v_2$$$ such that there is an edge between $$$u$$$ and $$$v_1$$$ and no edge between $$$u$$$ and $$$v_2$$$. Then remove the edge between $$$u$$$ and $$$v_1$$$ and add an edge between $$$u$$$ and $$$v_2$$$. This operation cannot be performed if the graph is no longer a tree after it.

Somehow Timofey managed to find out all the $$$d_i$$$. After that, he had another brilliant idea — just in case, make an instruction manual for the set, one that Alex wouldn't be disappointed.

Timofey is not as lazy as Alex, but when he saw the integer $$$n$$$, he quickly lost the desire to develop the instruction and the original tree, so he assigned this task to you. It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.

$\text{[math]}$

Here is an example of an operation where vertices were selected: $$$u$$$ — $$$6$$$, $$$v_1$$$ — $$$1$$$, $$$v_2$$$ — $$$4$$$.

Input

The first line contains the integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$3 \leq n \leq 500$$$) and $$$q$$$ ($$$1 \leq q \leq 500$$$) — the number of nodes in the tree and the number of days, respectively.

The $$$i$$$th of the following $$$q$$$ lines contains the integer $$$d_i$$$ ($$$2 \leq d_i \leq n - 1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$. The same is guaranteed for $$$q$$$.

It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.

Output

For each test case, first print an $$$n - 1$$$ string describing the edges of the tree. If you want the tree to have an edge between nodes $$$u$$$ and $$$v$$$, there must be a string $$$v$$$ $$$u$$$ or $$$u$$$ $$$v$$$ among these $$$n - 1$$$ lines.

In the next $$$q$$$ lines, print three integers each $$$u$$$ $$$v_1$$$ $$$v_2$$$ — a description of the operations. If Alex doesn't need to perform an operation the following day, print $$$-1$$$ $$$-1$$$ $$$-1$$$.

Idx	Name	Rating
A	Game with Integers	800
B	250 Thousand Tons of TNT	1100
C	Yarik and Array	1100
D	Yarik and Musical Notes	1300
E	Queue Sort	1300
F	Alex's whims	1600
G	Unusual Entertainment	1900

Codeforces Round 909 (Div. 3)