很久以前，Horus 和 Seth 为了争夺 Osiris 的王位继承权而展开了斗争。他们的争端由 Raa 进行裁决，Raa 给他们出了一系列挑战，以确定谁更有资格继承王位。Horus 成功赢得了所有的挑战，但 Raa 因为 Horus 年纪尚轻，仍不确定他是否有资格统治埃及。因此，Raa 决定给 Horus 最后一次挑战，以证明他的实力并彻底解决这场争斗。

Horus 的最后挑战是收集散布在埃及各地的 $N$ 个宝藏箱，编号从 $0$ 到 $N - 1$。宝藏箱的位置以二维平面上的点给出，且两两不同。具体来说，第 $i$ 个宝藏箱（$0 \le i < N$）的位置是一个点 $(X[i], Y[i])$，其中 $X[i]$ 和 $Y[i]$ 均为 $0$ 到 $5 \cdot 10^8$ 之间的整数（包含边界）。

Horus 打算通过在他的莎草纸笔记本上做笔记来记录宝藏箱的位置。笔记本的每一页可以存储一个不超过 $2 \cdot 10^9$ 的非负整数。遗憾的是，在 Horus 记完所有笔记后，Seth 会打乱这些笔记本页面。

你的任务是帮助 Horus 实现两个过程： 通过在笔记本页面上书写数字来记录宝藏箱的位置； 在给定被打乱顺序的笔记本页面的情况下，恢复宝藏箱的位置。

注意，你在本题中的得分取决于所使用的页面数量，即笔记本上书写的数字个数。

实现细节

你需要实现以下两个过程：

std::vector<int> encode(std::vector<std::pair<int, int>> P)

• $P$：长度为 $N$ 的数组，指定了宝藏箱的位置。元素 $P[i]$（对于 $0 \le i < N$）是一个二元组 $(X[i], Y[i])$，表示第 $i$ 个宝藏箱的位置。
• 该过程应返回一个数组 $E$，表示要写在 Horus 笔记本上的数字。数组中的每个元素都是写在笔记本页面上的数字，必须是 $0$ 到 $2 \cdot 10^9$ 之间的整数（包含边界）。
• 每个测试用例中，该过程可能会被调用多次。每次调用代表一个不同的场景。

std::vector<std::pair<int, int>> decode(std::vector<int> S)

• $S$：整数数组。该数组是 encode 过程返回数组的打乱版本，即它具有相同的长度和相同的元素，但顺序可能不同。
• 该过程应返回一个长度为 $N$ 的数组 $D$，指定宝藏箱的位置。数组 $D$ 中的每个元素应为一个二元组 $(x', y')$，表示一个宝藏箱的位置。
• 数组 $D$ 中的元素可以是任意顺序。

令 $T$ 为测试用例中的场景数量。评测系统会对每个场景调用一次 encode 过程。encode 过程返回的 $T$ 个数组随后会被评测系统打乱并提供给 decode 过程。注意，encode 和 decode 过程在评测系统中是在不同的程序中调用的。此外，场景在两个程序中的顺序不一定相同。

数据范围

• $1 \le T \le 100$
• $1 \le N \le 40\,000$
• $0 \le X[i] \le 5 \cdot 10^8$（$0 \le i < N$）
• $0 \le Y[i] \le 5 \cdot 10^8$（$0 \le i < N$）
• 没有两个宝藏箱位于相同的位置。
• 所有场景中的宝藏箱总数不超过 $2 \cdot 10^5$。
• 数组 $S$ 是 $E$ 的一个排列。

子任务与评分

你在本题中的得分取决于所使用的笔记本页面数量，即 encode 过程返回的数组 $E$ 的长度。对于给定的场景 $t$，令 $n_t$ 为宝藏箱的数量，$l_t$ 为 encode 过程返回的数组 $E$ 的长度。我们定义 $K$ 为所有场景中比率 $l_t / n_t$ 的最大值。

子任务 2 的得分根据 $K$ 计算如下：

样例

评测系统进行以下过程调用：

encode([(1, 5), (3, 2), (6, 3)])

在此样例中，有 3 个宝藏箱分别位于点 $(1, 5)$，$(3, 2)$ 和 $(6, 3)$。假设 Horus 在笔记本上写下的数字为 $E = [14, 18, 221, 457, 13]$。

然后，Seth 打乱了笔记本页面，将 $E$ 转换为数组 $S = [457, 18, 13, 221, 14]$。

评测系统随后进行以下过程调用：

decode([457, 18, 13, 221, 14])

Horus 推断出原始点为 $(3, 2)$，$(6, 3)$ 和 $(1, 5)$。因此，该过程返回数组 $D = [(3, 2), (6, 3), (1, 5)]$。注意，decode 过程返回点的顺序与 encode 过程提供的顺序不必相同。

样例评测程序

样例评测程序的输入以包含单个整数 $T$ 的行开始，后跟 $T$ 个场景。每个场景按以下格式提供：

N
X[0] Y[0]
X[1] Y[1]
...
X[N-1] Y[N-1]

样例评测程序按输入中提供的相同顺序写入每个场景的结果。每个场景的输出如下。令 $L$ 为场景中 encode 过程返回的数组 $E$ 的长度，$M$ 为 decode 过程返回的数组 $D$ 的长度（在正确解中，$M$ 必须等于 $N$）。此外，令 $X'[i] = D[i].first$ 且 $Y'[i] = D[i].second$，对于 $0 \le i < M$。样例评测程序按以下格式打印场景结果：

L
M
X'[0] Y'[0]
X'[1] Y'[1]
...
X'[M-1] Y'[M-1]

此外，如果场景中 encode 返回的数组包含无效元素，样例评测程序会打印 "Invalid element in the returned array" 并立即终止。