Sort an array of integers using a O(n^2) sorting algorithm.

Input

Input begins with n (1 ≤ n ≤ 1,000,000) of number integers in the array in a single line and followed by n lines having an integer in each line.

Output

Print the sorted array with one integer in each new line in ascending order.

Example

Input:
4
999999
0
-999999
1234

Output:
-999999
0
1234
999999