Гарри Поттер и Зал Пророчеств

Отряд Дамблдора готовится к полёту в Отдел Тайн Министерства Магии. Так как на их пути за Пророчеством могут встретиться слуги Волан-де-Морта, Гарри с Невиллом решили потренироваться в дуэльных боях.

Они решили провести $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$ чисел --- мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.