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.