B. Отсутствующий остаток
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана последовательность $$$a_1, a_2, \dots, a_n$$$, состоящая из $$$n$$$ попарно различных положительных чисел.

Найдите $$$\left\lfloor \frac n 2 \right\rfloor$$$ различных пар целых чисел $$$x$$$ и $$$y$$$ таких, что:

  • $$$x \neq y$$$;
  • $$$x$$$ и $$$y$$$ встречаются в $$$a$$$;
  • $$$x~mod~y$$$ не встречается в $$$a$$$.

Обратите внимание, что некоторые $$$x$$$ или $$$y$$$ могут входить в несколько пар.

$$$\lfloor x \rfloor$$$ обозначает функцию округления вниз — наибольшее целое число меньше либо равное $$$x$$$. $$$x~mod~y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

Если существует несколько решений, выведите любое из них. Можно показать, что решение всегда существует.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина последовательности.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Все числа в последовательности попарно различные. Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Ответ на каждый набор входных данных должен содержать $$$\left\lfloor \frac n 2 \right\rfloor$$$ различных пар целых чисел $$$x$$$ и $$$y$$$ таких, что $$$x \neq y$$$, $$$x$$$ и $$$y$$$ встречаются в $$$a$$$ и $$$x~mod~y$$$ не встречается в $$$a$$$. Выведите пары одну за другой.

Можно выводить пары в любом порядке. Однако, внутри пары числа должны быть такие, что первое число — это $$$x$$$, а второе число — это $$$y$$$. Все пары должны быть попарно различны.

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

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

В первом наборе входных данных существует только две пары: $$$(1, 4)$$$ и $$$(4, 1)$$$. $$$\left\lfloor \frac 2 2 \right\rfloor=1$$$, поэтому надо найти одну пару. $$$1~mod~4=1$$$, и $$$1$$$ встречается в $$$a$$$, поэтому такая пара некорректная. Поэтому единственный возможный ответ — это пара $$$(4, 1)$$$.

Во втором наборе входных данных мы выбрали пары $$$8~mod~2=0$$$ и $$$8~mod~4=0$$$. $$$0$$$ не входит в $$$a$$$, поэтому такой ответ правильный. В данном тесте существуют несколько решений.

В третьем наборе входных данных выбранные пары — $$$9~mod~5=4$$$ и $$$7~mod~5=2$$$. Ни $$$4$$$, ни $$$2$$$ не встречаются в $$$a$$$, поэтому такой ответ правильный.