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

시간 제한2초메모리 제한1024 MB

요약

매 라운드마다 가장 가까운 두 마법약을 고르고, 동률이면 합이 큰 쌍을 골라 누가 어느 것을 마시는지 순서대로 출력한다.

난이도: 보통10점 중 7점
유형: 정렬, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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

Они решили провести $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
1 2 4 8
```
예상 출력
```
2 8
1 4
```
예제 2
입력
```
3
23 42 42 23 1 2
```
예상 출력
```
42 23 2
42 23 1
```