我们为两个正整数 $$$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})$$$ 包含$$$^{\text{*}}$$$。
例如,对于$$$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$$$ 的余数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,如果可以排列序列 $$$b$$$ 的元素,以便存在一对合适的正整数 $$$x \geq y$$$,则在单独的行上输出 $$$x, y$$$。否则,在单独的行上输出 $$$-1$$$。
如果有几个合适的对 $$$x, y$$$,你可以输出其中任何一个。
示例
输入复制
621 121 241 2 3 436 4 243 8 13 531 1 1
输出复制
1 12 1-16 413 8-1
注意
在第一个测试用例中,对 ($$$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$$$ 得到。