Game on Ranges

题意翻译

Alice 和 Bob 是两个绝顶聪明的好朋友，他们总会聚在一起玩游戏。 今天，Alice 和 Bob 在玩一个和区间有关的有趣的游戏。他们手上有一个集合 $S$，里面一开始只有一个区间 $[1,n]$。我们定义一个区间 $[a,b]$ 是合法的，当且仅当 $a\leqslant b$。在每一步操作中，Alice 可以从集合 $S$ 中选出一个区间 $[l,r]$，然后让 Bob 在这个区间中选择一个整数 $d$，Alice 随后会把区间 $[l,r]$ 从集合 $S$ 里面拿出，放入区间 $[l,d-1]$ 和 $[d+1,r]$ 中所有合法的区间。当集合 $S$ 为空时，游戏结束。我们不难发现这个游戏进行了恰好 $n$ 次操作。 游戏之后，Alice 记得所有她取出来的区间 $[l,r]$ 但是**不记得取这些区间的先后顺序**，而 Bob 完全忘记了他从每个区间中取出的整数 $d$。然而众所周知，Bob 是绝顶聪明的，因此他知道他可以根据 Alice 取出的区间来判断他在每个区间中选出了哪个整数 $d$。现在，请你帮助 Bob 完成这个工作。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 1000$。 - $1\leqslant n,\sum n\leqslant 1000$，$1\leqslant l\leqslant r\leqslant n$。 - 保证数据合法并且答案唯一。 Translated by Eason_AC 2021.12.29

题目描述

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.

输入输出样例

输入样例 #1

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

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] $ . - 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)