← 返回题目列表

Codeforces · 2037/B

B. 截获的输入

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

为了帮助您为即将到来的 Codeforces 竞赛做好准备,Citlili 设置了一个网格问题,并尝试通过您的输入流为您提供 $$$n$$$ by $$$m$$$ 网格。具体来说,您的输入流应包含以下内容:

- 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ — 网格的尺寸。
- 以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数 — 网格的值。

然而,有人拦截了你的输入流,打乱了所有给定的整数,并将它们全部放在一行上!现在,一行中有$$$k$$$ 个整数,并且你不知道每个整数最初属于哪里。您决定自己确定 $$$n$$$ 和 $$$m$$$ 的值,而不是要求 Citlali 重新发送输入。

输出 Citlali 可能提供的 $$$n$$$ 和 $$$m$$$ 的任何可能值。

输入

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

每个测试用例的第一行包含一个整数 $$$k$$$ ($$$3 \leq k \leq 2 \cdot 10^5$$$) — 输入流中的输入总数。

每个测试用例的以下行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \leq a_i \leq k$$$) — 输入流的打乱输入。保证 $$$n$$$ 和 $$$m$$$ 包含在 $$$k$$$ 整数内。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出两个整数,一个可能的值 $$$n$$$ 和 $$$m$$$。如果存在多个可能的答案,则输出任何一个。

示例

输入 #1

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

输出 #1

1 1
3 3
2 3
4 1
1 6

注意

在第一个测试用例中,初始输入可能如下:

1 1

2

在第二个测试用例中,初始输入可能如下:

3 3

4 5 6

7 8 9

9 10 11