Given the list of numbers, you are to sort them in non decreasing order.


Input
t – the number of numbers in list, then t lines follow [t <= 10^6]. 
Each line contains one integer: N [0 <= N <= 10^6]


Output
Output given numbers in non decreasing order.

Example
Input:

5
5
3
6
7
1

Output:

1
3
5
6
7
def merge(a,b):
    out = []
    j = 0
    k = 0
    while (j<len(a) and k<len(b)):
        out.append(min(a[j],b[k]))
        if min(a[j],b[k]) == a[j]:
            j = j+1
        else:
            k = k+1
    while(j<len(a)):
       out.append(a[j])
       j = j+1
    while (k<len(b)):
        out.append(b[k])
        k = k+1
    return out
    
def msort(a):
    if len(a) == 1:
        return a
    else :
        return merge(msort(a[0:len(a)/2]),msort(a[len(a)/2:]))

def main():
    arr = []
    cases = int(raw_input())
    for i in range(cases):
        arr.append(int(raw_input()))
    arr = msort(arr)
    for i in arr:
        print i

if __name__ == '__main__':
    main()