Sorting with priority queues P40558

Statement

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.

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

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