C. Прямоугольник минимальной стоимости
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ палочек заданных длин.

Ваша задача — выбрать ровно четыре из них таким образом, чтобы они могли образовать прямоугольник. Никакие палочки нельзя резать на части, каждая сторона прямоугольника должна быть образована ровно одной палочкой. Никакую палочку нельзя брать несколько раз. Гарантируется, что всегда возможно выбрать такие палочки.

Пусть $$$S$$$ будет площадью прямоугольника, а $$$P$$$ — его периметром.

Выбранный прямоугольник должен иметь минимально возможное значение $$$\frac{P^2}{S}$$$. К значению не применяется никакое округление.

Если существует несколько ответов, выведите любой из них.

В каждом тесте содержится несколько списков палочек, для каждого из них необходимо решить задачу независимо.

Входные данные

В первой строке записано одно целое число $$$T$$$ ($$$T \ge 1$$$) — количество списков палочек в тесте.

Затем следуют $$$2T$$$ строк — строки $$$(2i - 1)$$$ и $$$2i$$$ из них описывают $$$i$$$-й список. В первой строке пары записано одно целое число $$$n$$$ ($$$4 \le n \le 10^6$$$) — количество палочек в $$$i$$$-м списке. Во второй строке пары записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_j \le 10^4$$$) — длины палочек в $$$i$$$-м списке.

Гарантируется, что для каждого списка существует способ выбрать четыре палочки таким образом, чтобы они образовывали прямоугольник.

Суммарное количество палочек во всех $$$T$$$ списках не превосходит $$$10^6$$$ в каждом тесте.

Выходные данные

Выведите $$$T$$$ строк. В $$$i$$$-й строке должен содержаться ответ для $$$i$$$-го списка входных данных. Ответ — это длины четырех палочек, которые надо выбрать из $$$i$$$-го списка, чтобы они образовывали прямоугольник и чтобы значение $$$\frac{P^2}{S}$$$ этого прямоугольника было минимально возможным. Эти длины можно выводить в произвольном порядке.

Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
3
4
7 2 2 7
8
2 8 1 4 8 2 1 5
5
5 5 5 5 5
Выходные данные
2 7 7 2
2 2 1 1
5 5 5 5
Примечание

В первом списке существует только один способ выбрать четыре палочки, они образуют прямоугольник со сторонами $$$2$$$ и $$$7$$$, его площадь равна $$$2 \cdot 7 = 14$$$, периметр равен $$$2(2 + 7) = 18$$$. $$$\frac{18^2}{14} \approx 23.143$$$.

Второй список содержит поднаборы из четырех палочек, которые могут образовать прямоугольники со сторонами $$$(1, 2)$$$, $$$(2, 8)$$$ и $$$(1, 8)$$$. Их значения — $$$\frac{6^2}{2} = 18$$$, $$$\frac{20^2}{16} = 25$$$ и $$$\frac{18^2}{8} = 40.5$$$, соответственно. Минимальное из них у прямоугольника $$$(1, 2)$$$.

В третьем списке можно выбрать любые четыре из $$$5$$$ данных палочек, они образуют квадрат со стороной $$$5$$$, что все еще прямоугольник со сторонами $$$(5, 5)$$$.