Harry Potter and the Hall of Prophecy

Interview

Time limit2sMemory limit1024 MB

Summary

Repeatedly pick the closest remaining pair of 2n potions (ties go to the larger sum) and print the stronger of each pair for Neville and the weaker for Harry.

Level: Medium5 of 10
Topics: Sorting, Heap, Linked list, Greedy
Solved: No attempts yet

Statement

Dumbledore's army is getting ready to fly to the Department of Mysteries at the Ministry of Magic. Voldemort's servants may be waiting on the way to the Prophecy, so Harry and Neville have decided to practice dueling.

They plan to hold $n$ rounds of duels. After each round, they drink a restorative potion so they do not waste strength. In total they have $2n$ potions. After each round, they pick two potions whose powers are closest to each other. If several such pairs exist, they choose the pair with the largest sum of powers. Then Neville drinks the stronger potion of the pair, and Harry drinks the weaker one.

Help Harry and Neville determine which potions each of them drinks and in what order.

Input

The first line contains one integer $n$ ( $1 \le n \le 100000$ ), the number of duel rounds. The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ( $1 \le a_i \le 10^9$ ), where $a_i$ is the power of the $i$ -th restorative potion.

Output

On the first line, print the $n$ powers of the potions that Neville drinks. On the second line, print the $n$ powers of the potions that Harry drinks. The potions must be printed in the order in which Neville and Harry drink them.

Examples2

Example 1
Input
```
2
1 2 4 8
```
Expected output
```
2 8
1 4
```
Example 2
Input
```
3
23 42 42 23 1 2
```
Expected output
```
42 23 2
42 23 1
```