U652248 [YCU Cup] 威汉森的“摸鱼”策略

寒假集训期间，**Aerhuo** 给队员们布置了海量的题目。为了提高效率（其实是为了偷懒），**威汉森** 向 **HM** 提议进行“双人结对编程”。 现有 $2n$ 道题目，每道题都有一个难度值 $w_i$。 威汉森提出了一种结对规则： 1. 将这 $2n$ 道题目两两配对，组成 $n$ 组。 2. 对于每一组题目，两人会优先解决**难度较小**的那一道，而把难度较大的那一道留着“以后再说”（其实就是不写了）。 3. 因此，每一组题目的**有效训练量**等于其中**较小**的那个难度值。 **Aerhuo** 发现了威汉森的小九九，但他决定反其道而行之。他要求威汉森设计一种配对方案，使得这 $n$ 组题目的**有效训练量之和最大**。如果不按照这个方案来，威汉森今天就别想去玩 Galgame 了。

给定 $2n$ 个整数 $w_1, w_2, \dots, w_{2n}$，代表 $2n$ 道题目的难度。 请你将它们两两配对，使得所有对子的 $\min(a, b)$ 之和最大。 为了方便核对，请按照每组的有效训练量（即较小值）**从小到大**的顺序输出这 $n$ 个对子。 **本题包含多组测试数据。**

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试数据的组数。 接下来对于每组测试数据： - 第一行包含一个整数 $n$，表示题目的对数（总题目数为 $2n$）。 - 第二行包含 $2n$ 个整数 $w_i$，表示每道题的难度。

对于每组测试数据： - 输出 $n$ 行。 - 每行两个整数，表示一对题目的难度值。先输出较小的，再输出较大的。 - **要求**：这 $n$ 行的输出顺序，必须按照每行的第一个数（较小值）从小到大排列。

**威汉森**：“把简单的和难的配一对，这样我只用做简单的，难的就混过去了，嘿嘿。” **HM**：“可是 Aerhuo 让你总训练量最大，你这样配，大的数字全被浪费了。” **威汉森**：“啊？” ## 数据范围 对于 $100\%$ 的数据， $1 \le T \le 10$， $1 \le n \le 10^5$，单测试点数据的 $n$ 之和 $\sum n \le 2 \cdot 10^5$。 $1 \le w_i \le 10^9$。