Game on Ranges

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

Each of the next $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), denoting the range $$$[l, r]$$$ that Alice picked at some point.

Note that the ranges are given in no particular order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the ranges for each test case are from a valid game.

Output:

For each test case print $$$n$$$ lines. Each line should contain three integers $$$l$$$, $$$r$$$, and $$$d$$$, denoting that for Alice's range $$$[l, r]$$$ Bob picked the number $$$d$$$.

You can print the lines in any order. We can show that the answer is unique.

It is not required to print a new line after each test case. The new lines in the output of the example are for readability only.

Sample Input:

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

Sample Output:

1 1 1

1 3 1
2 2 2
2 3 3

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

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

Note:

In the first test case, there is only 1 range $$$[1, 1]$$$. There was only one range $$$[1, 1]$$$ for Alice to pick, and there was only one number $$$1$$$ for Bob to pick.

In the second test case, $$$n = 3$$$. Initially, the set contains only one range $$$[1, 3]$$$.

• Alice picked the range $$$[1, 3]$$$. Bob picked the number $$$1$$$. Then Alice put the range $$$[2, 3]$$$ back to the set, which after this turn is the only range in the set.
• Alice picked the range $$$[2, 3]$$$. Bob picked the number $$$3$$$. Then Alice put the range $$$[2, 2]$$$ back to the set.
• Alice picked the range $$$[2, 2]$$$. Bob picked the number $$$2$$$. The game ended.

In the fourth test case, the game was played with $$$n = 5$$$. Initially, the set contains only one range $$$[1, 5]$$$. The game's turn is described in the following table.

Game turn	Alice's picked range	Bob's picked number	The range set after
Before the game start			$$$ \{ [1, 5] \} $$$
1	$$$[1, 5]$$$	$$$3$$$	$$$ \{ [1, 2], [4, 5] \}$$$
2	$$$[1, 2]$$$	$$$1$$$	$$$ \{ [2, 2], [4, 5] \} $$$
3	$$$[4, 5]$$$	$$$5$$$	$$$ \{ [2, 2], [4, 4] \} $$$
4	$$$[2, 2]$$$	$$$2$$$	$$$ \{ [4, 4] \} $$$
5	$$$[4, 4]$$$	$$$4$$$	$$$ \{ \} $$$ (empty set)