| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 2 | 2 | 40.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$ чисел --- мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.
2 1 2 4 8
2 8 1 4
3 23 42 42 23 1 2
42 23 2 42 23 1