The Sketchy Government Spying Organization (SGSO) has released a new blockchain, but you're skeptical of its security. To show that it's insecure, you need to be able to quickly solve the proof-of-work problem on your weak computer.

The proof-of-work problem is:

Given an integer ~N~, followed by ~N~ integers in the range ~[0, 100\,000]~ (each on its own line), output the ~N~ integers in ascending order.

Input Specification

The first line contains the integer ~N~ ~(1 \leq N \leq 5 \times 10^6)~.

The next ~N~ lines each contain an integer in the range ~[0, 100\,000]~.

Output Specification

Print the ~N~ integers in ascending order, with one integer per line.

Sample Input 1

5
9
2
2
1
10

Sample Output 1

1
2
2
9
10