Teacups

After a successful tea party, Anatol is left with $N$ ($1 \le N \le 100,000$) teacups that he needs to put away. Anatol's teacups feature colourful designs of integers; specifically the $i$-th teacup has an integer $t_i$ ($1 \le t_i \le 1,000,000$) written on it. Anatol's teacups are supposed come in pairs of two teacups which have the same integer (no two pairs will have the same integer), but unfortunately some of his teacups seem to have gone missing.

Anatol has two very long shelves on which he stores his teacups. His approach to storing his teacups is certainly peculiar. On the first shelf he stores the teacups which have their pair in sorted order, and on the second shelf he stores the remaining teacups in sorted order.

Anatol has asked for your help to write a program to figure out how the teacups should be arranged on his shelves.

Input

The first line contains a single integer $N$.

The following $N$ lines each contain the number of each teacup, $t_1, t_2, \dots, t_N$, each on their own line.

Output

Output exactly two lines. On the first line output Shelf 1: followed by the space separated teacups on shelf 1 (possibly none).

On the second line output Shelf 2: followed by the space separated teacups on shelf 2 (possibly none).

Subtasks

• Subtask 1 (24%): $N \le 1,000$
• Subtask 2 (33%): Every teacup has a pair.
• Subtask 3 (43%): No further constraints.

Sample Explanation

Sample 1

In this sample the teacups with labels $2$ and $3$ both have a pair so they end up on the first shelf. The teacup with label $1$ has no pair so it ends up on the second shelf. This sample would be a valid test case for Subtask 1 and Subtask 3.

Sample 2

In this sample all the teacups have a pair, so they all end up on the second shelf. This sample would be a valid test case for all subtasks.