Blackwater Industries 计划在半人马座 $\alpha$ A 星系的森林卫星潘多拉上建造一个太空殖民地，并聘请你提供帮助。

该殖民地将由 $n$ 个高度为正整数的穹顶组成。这 $n$ 个穹顶将排成一个序列，我们从左到右将位置标记为 $1$ 到 $n$。利用虫洞技术的最新进展，可以在任意两个现有穹顶之间插入一个新穹顶，即使它们之间没有可用空间！当然，也可以在第一个穹顶之前或最后一个穹顶之后插入新穹顶。

太空殖民地将从一个空序列开始，分 $n$ 个步骤建造。第 $i$ 步由两个整数 $(p_i, h_i)$ 描述，其含义如下：

• 插入一个高度为 $h_i$ 的新穹顶，使得插入后该穹顶位于位置 $p_i$。

更正式地说，在第 $i$ 步之前，序列中恰好有 $i-1$ 个穹顶，第 $i$ 次操作 $(p_i, h_i)$ 必须满足 $1 \le p_i \le i$。此时第 $i$ 次操作的含义为：

• 如果 $p_i = 1$，则在所有现有穹顶之前插入一个高度为 $h_i$ 的新穹顶。
• 如果 $p_i = i$，则在所有现有穹顶之后插入一个高度为 $h_i$ 的新穹顶。
• 如果 $1 < p_i < i$，则在位置 $p_i-1$ 和 $p_i$ 的穹顶之间插入一个高度为 $h_i$ 的新穹顶。

因此，在第 $i$ 步之后，序列中恰好有 $i$ 个穹顶。

对于一个包含 $2n$ 个数字的序列 $S = [p_1, h_1, p_2, h_2, \dots, p_n, h_n]$，定义 $C(S)$ 为执行操作序列 $(p_1, h_1), (p_2, h_2), \dots, (p_n, h_n)$ 后穹顶的高度序列。因此，$C(S)$ 是一个包含 $n$ 个数字的序列。

Blackwater Industries 已经起草了一份初步计划。他们的目标是建造一个穹顶高度等于 $C(P)$ 的太空殖民地，其中 $P$ 是作为输入给出的 $2n$ 个数字的序列。然而，他们很吝啬，所以他们想以更低的成本建造同一个太空殖民地！

在太空旅行时代，成本的衡量方式有所不同。对于给定的两个长度为 $2n$ 的序列 $P$ 和 $Q$，成本较低的序列是字典序较小的那个。

什么是产生与 $P$ 相同的太空殖民地的最廉价的 $Q$？换句话说，满足 $C(P) = C(Q)$ 的字典序最小的 $2n$ 个数字的序列 $Q$ 是什么？

说明：设 $A$ 和 $B$ 为两个不同的序列。当且仅当满足以下至少一个条件时，$A$ 的字典序小于 $B$：

• $A$ 是 $B$ 的前缀；
• $A$ 不是 $B$ 的前缀，且在第一个不同的位置 $i$ 上，$A_i < B_i$。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例包含多行输入。第一行包含整数 $n$。接下来 $n$ 行，其中第 $i$ 行包含两个空格分隔的整数 $p_i$ 和 $h_i$。序列 $P$ 定义为 $[p_1, h_1, p_2, h_2, \dots, p_n, h_n]$。

• $1 \le t \le 1000$
• $1 \le n \le 500000$
• 单个测试文件中所有 $n$ 的总和不超过 $500000$
• $1 \le p_i \le i$
• $1 \le h_i \le n$

输出格式

对于每个测试用例，输出 $n$ 行，其中第 $i$ 行包含两个空格分隔的整数 $P_i$ 和 $H_i$。定义的序列 $Q = [P_1, H_1, P_2, H_2, \dots, P_n, H_n]$ 必须是满足 $C(P) = C(Q)$ 的字典序最小的序列。

样例

输入 1

1
3
1 1
2 2
1 3

输出 1

1 1
1 3
3 2

说明

输出中的序列 $P = [1, 1, 2, 2, 1, 3]$ 对应于 3 次操作 $(1, 1), (2, 2), (1, 3)$，产生以下高度序列：

• 初始时，序列为 []（空）。
• 执行 $(1, 1)$ 后，高度为 [1]。
• 执行 $(2, 2)$ 后，高度为 [1, 2]。
• 执行 $(1, 3)$ 后，高度为 [3, 1, 2]。

因此，$C(P) = [3, 1, 2]$。

输出中的序列 $Q = [1, 1, 1, 3, 3, 2]$ 对应于 3 次操作 $(1, 1), (1, 3), (3, 2)$，产生以下高度序列：

• 初始时，序列为 []（空）。
• 执行 $(1, 1)$ 后，高度为 [1]。
• 执行 $(1, 3)$ 后，高度为 [3, 1]。
• 执行 $(3, 2)$ 后，高度为 [3, 1, 2]。

因此，$C(Q) = [3, 1, 2]$，且我们有 $C(P) = C(Q)$。此外，可以证明 $[1, 1, 1, 3, 3, 2]$ 是满足条件的字典序最小的序列。