CF1623B Game on Ranges

Alice 和 Bob 玩如下游戏。Alice 有一个整数区间集合 $S$，最开始只包含一个区间 $[1, n]$。每一回合，Alice 从集合 $S$ 中选出一个区间 $[l, r]$，让 Bob 从该区间中选一个数。Bob 选择一个数 $d$（$l \le d \le r$）。然后 Alice 将 $[l, r]$ 从 $S$ 中移除，并将 $[l, d-1]$（如果 $l \le d-1$）和 $[d+1, r]$（如果 $d+1 \le r$）加入 $S$。当 $S$ 为空时，游戏结束。可以证明，每次游戏的回合数恰好为 $n$。 游戏结束后，Alice 记得她每次从 $S$ 中选出的所有区间 $[l, r]$，但 Bob 不记得他选的任何数字。不过 Bob 很聪明，他知道可以通过 Alice 选出的区间推断出他选的数字 $d$，于是他请求你用编程帮他找出每个区间对应的 $d$。 给定 Alice 选出的所有区间 $[l, r]$ 的列表，对于每个区间，帮助 Bob 找出他当时选的数字 $d$。 可以证明，对于每组有效的区间列表，Bob 选择数字的方式是唯一的。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 1000$）。 接下来的 $n$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示 Alice 某次选出的区间 $[l, r]$。 注意，这些区间的顺序是无序的。 保证所有测试数据中 $n$ 的总和不超过 $1000$，且每组区间均来自一次有效的游戏过程。

对于每组测试数据，输出 $n$ 行。每行输出三个整数 $l$、$r$ 和 $d$，表示对于 Alice 的区间 $[l, r]$，Bob 选择的数字 $d$。 输出的行顺序可以任意。可以证明答案是唯一的。 每组测试数据之间不需要额外换行。样例输出中的换行仅为可读性。

在第一个测试点中，只有一个区间 $[1, 1]$。Alice 只能选 $[1, 1]$，Bob 也只能选 $1$。 在第二个测试点中，$n=3$。最开始集合只包含区间 $[1, 3]$。 - Alice 选 $[1, 3]$，Bob 选 $1$。Alice 将 $[2, 3]$ 放回集合，此时集合只剩 $[2, 3]$。 - Alice 选 $[2, 3]$，Bob 选 $3$。Alice 将 $[2, 2]$ 放回集合。 - Alice 选 $[2, 2]$，Bob 选 $2$。游戏结束。 在第四个测试点中，$n=5$。最开始集合只包含区间 $[1, 5]$。游戏过程如下表所示。 | 回合 | Alice 选的区间 | Bob 选的数字 | 回合后集合 | |:---:|:--------------:|:------------:|:----------:| | 游戏开始前 | — | — | $\{[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$ | $\{\}$（空集） | 由 ChatGPT 4.1 翻译