시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB62240.000%

문제

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

Они решили провести $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

2
1 2 4 8

예제 출력 1

2 8
1 4

예제 입력 2

3
23 42 42 23 1 2

예제 출력 2

42 23 2
42 23 1