A14836. Game on Ranges

Alice and Bob play the following game. Alice has a set $S$ of disjoint ranges of integers, initially containing only one range $[1, n]$ . In one turn, Alice picks a range $[l, r]$ from the set $S$ and asks Bob to pick a number in the range. Bob chooses a number $d$ ( $l \le d \le r$ ). Then Alice removes $[l, r]$ from $S$ and puts into the set $S$ the range $[l, d - 1]$ (if $l \le d - 1$ ) and the range $[d + 1, r]$ (if $d + 1 \le r$ ). The game ends when the set $S$ is empty. We can show that the number of turns in each game is exactly $n$ .

After playing the game, Alice remembers all the ranges $[l, r]$ she picked from the set $S$ , but Bob does not remember any of the numbers that he picked. But Bob is smart, and he knows he can find out his numbers $d$ from Alice's ranges, and so he asks you for help with your programming skill.

Given the list of ranges that Alice has picked ( $[l, r]$ ), for each range, help Bob find the number $d$ that Bob has picked.

We can show that there is always a unique way for Bob to choose his number for a list of valid ranges picked by Alice.

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.

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.

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 turnAlice's picked rangeBob's picked numberThe range set afterBefore 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)