A. Евклид, последовательность, два числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим последовательность алгоритма Евклида длины $$$k$$$ ($$$k \geq 2$$$) для двух целых положительных чисел $$$x \geq y$$$ следующей последовательностью положительных чисел:

  • $$$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$$$ несколько, то можно вывести любую из них.

Пример
Входные данные
6
2
1 1
2
1 2
4
1 2 3 4
3
6 4 2
4
3 8 13 5
3
1 1 1
Выходные данные
1 1
2 1
-1
6 4
13 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$$$.