Sorting with priority queues P40558

Statement

thehtml

Use priority queues to sort a sequence of integer numbers, in nondecreasing order and also in nonincreasing order.

Input

Input consists of a sequence of integer numbers.

Output

Print two lines, the first one with the numbers in increasing order, and the second one with the numbers in decreasing order.

Observation

To solve this exercise, the only containers that you should use are priority queues of integer numbers.

Public test cases

Input

17 2 5 11 19 13 7 3

Output

2 3 5 7 11 13 17 19
19 17 13 11 7 5 3 2

Input

2 4 6 4 2

Output

2 2 4 4 6
6 4 4 2 2

Information