Turbo Sort

Problem statement

A logistics centre receives parcel codes in the order their scanners report them. Before printing the dispatch index, staff need those codes arranged from smallest to largest. Duplicate codes are legitimate repeated records and must remain in the output. The input volume can be large, so this task also checks whether your program reads and writes a substantial list efficiently. Your task Read n integers, sort all of them in nondecreasing order, and print one integer per line. Do not discard duplicates or attach record numbers. The output must contain exactly n values, each drawn from the input with the same multiplicity. Important details An already sorted list should remain sorted. A reverse-sorted list needs the same treatment as any other. This is numeric order, so 10 follows 2 even though their text representations compare differently. Worked example For codes [9,2,9,1], the dispatch index lists 1, then 2, then 9, then 9. Both occurrences of 9 are retained.

Input format

First line: n. Following input: n integers.

Output format

Print the sorted values, one per line.

Constraints

1 <= n <= 1000000; 0 <= each value <= 1000000.

Sample input

4
9
2
9
1

Sample output

1
2
9
9