Задача №111582. Гарри Поттер и Зал Пророчеств
Отряд Дамблдора готовится к полёту в Отдел Тайн Министерства Магии. Так как на их пути за Пророчеством могут встретиться слуги Волан-де-Морта, Гарри с Невиллом решили потренироваться в дуэльных боях.
Они решили провести \(n\) раундов дуэли, а после каждого раунда выпивать восстанавливающее зелье, чтобы не тратить лишних сил. Всего у ребят \(2n\) зелий. После каждого раунда дуэли они выбирают два наиболее близких по мощности восстанавливающих зелья. Из нескольких таких пар они выбирают ту, у которой сумма мощностей наибольшая. Затем Невилл выпивает более мощное зелье из пары, а Гарри - менее мощное.
Помогите Гарри с Невиллом определить, какие зелья и в каком порядке выпьет каждый из них.
Первая строка входного файла содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) - количество раундов дуэли. Во второй строке входного файла содержится \(2n\) целых чисел \(a_1, a_2, \ldots, a_{2n}\) (\(1\le a_i \le 10^9\)), где \(a_i\) - мощность \(i\)-го восстанавливающего зелья.
В первой строке выведите \(n\) чисел - мощности зелий, которые выпьет Невилл. Во второй строке выведите \(n\) чисел - мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.
1 3 6
6 3
2 11 43 56 22
22 56 11 43