CF1623B.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.

爱丽丝和鲍勃玩以下游戏。爱丽丝持有一个互不相交的整数区间集合 $S$，初始时 $S$ 中仅包含一个区间 $[1, n]$。在每一轮中，爱丽丝从集合 $S$ 中选出一个区间 $[l, r]$，并请鲍勃从中选择一个整数。鲍勃选择一个数 $d$（满足 $l \le d \le r$）。随后，爱丽丝将 $[l, r]$ 从 $S$ 中移除，并向 $S$ 中加入区间 $[l, d - 1]$（若 $l \le d - 1$）和 $[d + 1, r]$（若 $d + 1 \le r$）。当集合 $S$ 为空时，游戏结束。可以证明：每局游戏的轮数恰好为 $n$。

游戏结束后，爱丽丝记得她从集合 $S$ 中选取的所有区间 $[l, r]$，但鲍勃却完全不记得自己所选的任何数字。不过鲍勃很聪明，他知道可以根据爱丽丝提供的这些区间推断出自己每次所选的数字 $d$，因此他请求你借助编程能力来帮助他。

给定爱丽丝所选取的区间列表（即一系列 $[l, r]$），对其中每一个区间，请帮鲍勃找出他当时所选的数字 $d$。

可以证明：对于爱丽丝给出的任意一组合法区间，鲍勃选择数字 $d$ 的方式总是唯一的。

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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 1000$）。

接下来的 $n$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示爱丽丝在某个时刻所选的区间 $[l, r]$。

注意：这些区间以任意顺序给出。

保证所有测试用例的 $n$ 值之和不超过 $1000$，且每个测试用例中的区间均来自一场合法的游戏。

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.

对每个测试用例，输出 $n$ 行。每行应包含三个整数 $l$、$r$ 和 $d$，表示对于 Alice 的区间 $[l, r]$，Bob 选择的数为 $d$。

各行的输出顺序可以任意。我们可以证明该答案是唯一的。

每个测试用例结束后无需额外输出换行符。示例输出中的换行仅为了提高可读性。

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)

在第一个测试用例中，只有一个区间 $[1, 1]$。爱丽丝只能选择这一个区间 $[1, 1]$，而鲍勃只能选择其中唯一的数字 $1$。

在第二个测试用例中，$n = 3$。初始时，集合中仅包含一个区间 $[1, 3]$。

• 爱丽丝选择了区间 $[1, 3]$，鲍勃选择了数字 $1$。随后爱丽丝将区间 $[2, 3]$ 放回集合中，此时该区间成为集合中唯一存在的区间。
• 爱丽丝选择了区间 $[2, 3]$，鲍勃选择了数字 $3$。随后爱丽丝将区间 $[2, 2]$ 放回集合中。
• 爱丽丝选择了区间 $[2, 2]$，鲍勃选择了数字 $2$。游戏结束。

在第四个测试用例中，游戏在 $n = 5$ 的条件下进行。初始时，集合中仅包含一个区间 $[1, 5]$。游戏各回合情况如下表所示。

游戏回合

爱丽丝选择的区间

鲍勃选择的数字

本轮操作后的区间集合

游戏开始前

$ { [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$

$ { } $（空集）