day-5-recursion
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

Problem

Bajirao wants to protect Guruji and for that he has arranged a special force
of expert officers. But Baba is also an intelligent enemy of Bajirao and he has
also arranged a bunch of expert shooters from foreign countries.

Every man has some experience points. In this scenario Bajirao's men have even experience points and Baba's men have odd experience points.

Now, Bajirao's strategy is to place his men in ascending order so that if enemy is going to attack then the more experienced men can easily takeover the enemy.

But Baba also has a stratergy. Baba will send his force in a descending
order of experience points so that their motive of killing Guruji will be
achieved , as, even if the more experienced ones die the less experienced ones can reach inside and kill Guruji.

Now, you have been given an array of experience points of
men and you have to find the men belonging to Bajirao's Force and
Baba's Force and print their experience points in appropriate order.

Input

It consists of 2 lines. The first line consists of a single integer N, the total number of men available to join the two forces. The next line comprises on N space separated integers, each integer denoting the experience points of a single man.

Ouput :

Ouput 2 lines. The first line comprises of space separated integers denoting the experience points of every man in Bajirao's Force in the appropriate order. The next line comprises of space-separated integers denoting the experience points of every man in Baba's force in the appropriate order.

Constraints :

1 ≤ N ≤ 1000

1 ≤ Experience Points ≤ 10^9

Problem Setter : Shreyans

Problem Tester : Sandeep

Problem Statement : Ravi

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
7
3 1 14 7 6 7 2

SAMPLE OUTPUT
2 6 14
7 7 3 1