← 返回题目列表

Codeforces · 1613/B

B. 剩余部分缺失

中文机器翻译题面 查看原题

给定一个序列 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 成对不同的正整数组成。

找到 $$$\left\lfloor \frac n 2 \right\rfloor$$$ 不同的整数对 $$$x$$$ 和 $$$y$$$ 使得:

- $$$x \neq y$$$;
- $$$x$$$ 和 $$$y$$$ 出现在 $$$a$$$ 中;
- $$$x~mod~y$$$ 没有出现在 $$$a$$$ 中。

请注意,某些 $$$x$$$ 或 $$$y$$$ 可以属于多个对。

$$$\lfloor x \rfloor$$$ 表示下取整函数 - 小于或等于 $$$x$$$ 的最大整数。 $$$x~mod~y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。

如果有多个解决方案,请打印其中任何一个。可以证明,至少总是存在一个解。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 序列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。

序列中的所有数字都是两两不同的。所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

每个测试用例的答案应包含 $$$\left\lfloor \frac n 2 \right\rfloor$$$ 不同的整数对 $$$x$$$ 和 $$$y$$$,使得 $$$x \neq y$$$、$$$x$$$ 和 $$$y$$$ 出现在 $$$a$$$ 中,而 $$$x~mod~y$$$ 不会出现在 $$$a$$$ 中出现在$$$a$$$中。逐一打印这些对。

您可以按任意顺序打印这些对。但是,该对中数字的顺序应该完全相同,即第一个数字是 $$$x$$$,第二个数字是 $$$y$$$。所有对都应该是两两不同的。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4
2
1 4
4
2 8 3 4
5
3 8 5 9 7
6
2 7 5 3 4 8

输出 #1

4 1
8 2
8 4
9 5
7 5
8 7
4 3
5 2

注意

在第一个测试用例中只有两对:$$$(1, 4)$$$ 和 $$$(4, 1)$$$。 $$$\left\lfloor \frac 2 2 \right\rfloor=1$$$,所以我们必须找到一对。 $$$1~mod~4=1$$$,并且$$$1$$$出现在$$$a$$$中,因此该对无效。因此,唯一可能的答案是一对 $$$(4, 1)$$$。

在第二个测试用例中,我们选择了 $$$8~mod~2=0$$$ 和 $$$8~mod~4=0$$$ 对。 $$$0$$$ 没有出现在 $$$a$$$ 中,因此该答案有效。该测试用例有多种可能的答案。

在第三个测试用例中,选择的对是 $$$9~mod~5=4$$$ 和 $$$7~mod~5=2$$$。 $$$4$$$ 和 $$$2$$$ 都没有出现在 $$$a$$$ 中,因此该答案有效。