CF2234A.Euclid, Sequence and Two Numbers

We define a Euclid algorithm sequence of length $k$ ($k \geq 2$) for two positive integers $x \geq y$ as the following sequence of positive integers:

• $a_1, a_2, \ldots, a_k$, where $a_1 = x$, $a_2 = y$, and for any $i$ ($1 \leq i \leq k - 2$), the equality $a_{i + 2} = (a_i \bmod a_{i + 1})$ holds$^{\text{∗}}$.

For example, for $x = 13, y = 8, k = 4$, the corresponding Euclid algorithm sequence is $a = [13, 8, 5, 3]$. ($a_3 = 13 \bmod 8 = 5$, $a_4 = 8 \bmod 5 = 3$).

You are given a sequence $b_1, b_2, \ldots, b_n$. You need to determine whether it is possible to permute its elements so that it becomes a Euclid algorithm sequence for some two positive integers $x \geq y$.

$^{\text{∗}}$$x \bmod y$ denotes the remainder when $x$ is divided by $y$.

我们定义两个正整数 $x \geq y$ 的长度为 $k$（$k \geq 2$）的欧几里得算法序列如下所示的正整数序列：

• $a_1, a_2, \ldots, a_k$，其中 $a_1 = x$，$a_2 = y$，且对任意 $i$（$1 \leq i \leq k - 2$），均满足 $a_{i + 2} = (a_i \bmod a_{i + 1})$。

例如，当 $x = 13$、$y = 8$、$k = 4$ 时，对应的欧几里得算法序列为 $a = [13, 8, 5, 3]$。（$a_3 = 13 \bmod 8 = 5$，$a_4 = 8 \bmod 5 = 3$）

给定一个序列 $b_1, b_2, \ldots, b_n$。你需要判断：是否可能重排该序列的元素，使其成为某个正整数对 $x \geq y$ 对应的欧几里得算法序列。

$^{\text{∗}}$$x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 100$) — the size of the sequence.

The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$) — the sequence $b$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 100$）—— 序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$）—— 序列 $b$。

For each test case, if it is possible to permute the elements of sequence $b$ so that there exists a suitable pair of positive integers $x \geq y$, output $x, y$ on a separate line. Otherwise, output $-1$ on a separate line.

If there are several suitable pairs $x, y$, you may output any of them.

对于每个测试用例，如果可以对序列 $b$ 的元素进行重排，使得存在一对满足条件的正整数 $x \geq y$，则在单独一行输出 $x, y$；否则，在单独一行输出 $-1$。

如果存在多对满足条件的 $x, y$，则可输出其中任意一对。

In the first test case, the pair ($1, 1$) is suitable: for $x = 1, y = 1, k = 2$, $a_1 = x = 1, a_2 = y = 1$, and the sequence $a = [1, 1] = b$ is obtained.

In the third test case, it can be shown that no suitable pair ($x, y$) exists.

In the fourth test case, the pair ($6, 4$) is suitable: for $x = 6, y = 4, k = 3$, $a_1 = x = 6, a_2 = y = 4, a_3 = (a_1 \bmod a_2) = (6 \bmod 4) = 2$, and the sequence $a = [6, 4, 2] = b$ is obtained.

在第一个测试用例中，数对 $(1, 1)$ 是可行的：当 $x = 1, y = 1, k = 2$ 时，有 $a_1 = x = 1, a_2 = y = 1$，从而得到序列 $a = [1, 1] = b$。

在第三个测试用例中，可以证明不存在可行的数对 $(x, y)$。

在第四个测试用例中，数对 $(6, 4)$ 是可行的：当 $x = 6, y = 4, k = 3$ 时，有 $a_1 = x = 6, a_2 = y = 4, a_3 = (a_1 \bmod a_2) = (6 \bmod 4) = 2$，从而得到序列 $a = [6, 4, 2] = b$。