Develop the Merge Sort algorithm on an integer list.

Input

• The first line is an integer ~N (1 ≤ N ≤ 10^6)~, the number of integers.
• The ith line of the next ~N~ lines contains the integer ~(0 ≤ n_i ≤ 10^9)~.

Output

• Output ~N~ rows, each row contains the integer in an ascending order.

Sample Input

5
5
4
1
0
3

Sample Output

0
1
3
4
5