Задана последовательность \(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\).
Если существует несколько решений, выведите любое из них. Можно показать, что решение всегда существует.
Выходные данные
Ответ на каждый набор входных данных должен содержать \(\left\lfloor \frac n 2 \right\rfloor\) различных пар целых чисел \(x\) и \(y\) таких, что \(x \neq y\), \(x\) и \(y\) встречаются в \(a\) и \(x~mod~y\) не встречается в \(a\). Выведите пары одну за другой.
Можно выводить пары в любом порядке. Однако, внутри пары числа должны быть такие, что первое число — это \(x\), а второе число — это \(y\). Все пары должны быть попарно различны.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных существует только две пары: \((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\), поэтому такой ответ правильный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|