Codeforces Round 763 (Div. 2) |
---|
Finished |
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.
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
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
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]$$$.
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) |
Name |
---|