e-olymp
Competitions

Ukrainian Olympiad in Informatics, II Stage, I Round

F. Антон та перфекціонізм

Антон отримав два масиви довжини $n$ кожний, де $n$ --- парне число. Він дуже хоче, щоб з цих масивів було утворено рівно $n$ пар чисел, які задовольняють наступним умовам: \begin{itemize} \item Перше число пари належить першому масиву, друге число --- другому. \item Числа в кожній парі різні. \item Рівно в половині пар перше число менше за друге. \end{itemize} Допоможіть Антону та знайдіть будь-який такий розподіл на $n$ пар. \InputFile Перший рядок містить парне число $n$ ($2 \leq n \leq 10^5$, $n$~--- парне). Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)~--- числа першого масиву. Третій рядок містить $n$ цілих чисел $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$)~--- другого масиву відповідно. \OutputFile Виведіть $n$ рядків, кожен з яких містить два цілі числа --- розбиття на пари, що задовольняє умовам. Якщо існує декілька рішень, то виведіть будь-яке з них. Якщо рішення не існує, то виведіть єдине ціле число $-1$. \Note У першому тесті наведена відповідь не є єдиною. У другому тесті легко переконатись, що неможливо знайти чотири пари чисел, які задовольняють умовам задачі.
Time limit 1 second
Memory limit 256 MiB
Input example #1
6
1 3 4 3 12 7
5 6 2 1 4 10
Output example #1
7 2
3 6
4 1
3 10
1 5
12 4
Input example #2
4
1 3 10 2
4 9 4 20
Output example #2
-1
Source Ukrainian Olympiad in Informatics, II Stage, I Round