Ограничение по времени: 3.000 секунд
Ограничение по памяти: 200.000 мегабайт
Вова и Сережа на корпоративе решили сыграть в игру на выпивание.
Они решили провести n раундов дуэли, в каждом раунде они выпивают по бокалу какого-либо напитка. Всего у ребят 2n разных напитков. В каждом раунде дуэли они выбирают два наиболее близких по объему напитка. Из нескольких таких пар они выбирают ту, у которой сумма объемов наибольшая. Затем Вова выпивает более объемный напиток из пары, а Сережа - менее объемный.
Помогите Вове и Сереже определить, какие напитки и в каком порядке выпьет каждый из них. Кстати, игра не подразумевает победителя, тут главное - процесс.
Первая строка содержит одно целое число n (1 ≤ n ≤ 100 000) - количество раундов дуэли. Во второй строке содержится 2n целых чисел a1, a2, ... , a2n (1 ≤ ai ≤ 109), где ai - объем i-го напитка.
В первой строке выведите n чисел - объемы напитков, которые выпьет Вова. Во второй строке выведите n чисел - объемы напитков, которые выпьет Сережа. Напитки надо выводить в том порядке, в котором Вова и Сережа должны их выпивать.
| input | output |
|---|---|
2 1 2 4 8 |
2 8 1 4 |
3 23 42 42 23 1 2 |
42 23 2 42 23 1 |