01204212/integer sorting

This is part of 01204212.

You are given N integers (whose values are between -1,000,000,000 to 1,000,000,000). You want to sort them ascendingly.

Input/Output

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains one integer

Output

Output N lines of N integers in sorted order from the smallest to the largest.

Example

Input

5
10
2
300
25
7

Output

2
7
10
25
300

Test data

Download them at: http://theory.cpe.ku.ac.th/~jittat/courses/01204212/tasks/sortint/

Correct answer for n10.in

22
172
189
245
266
332
399
597
858
984

Correct answer for n10000.in (first 10 lines:

71
83
131
188
261
265
368
399
464
495