PES16SO1 - Sort an array of integers using a O(n^2) algorithm

no tags 

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


Added by:Prof. Channa Bankapur
Date:2016-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C