题目描述

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]$。游戏过程如下表所示。

由 ChatGPT 4.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 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