다른 정렬과는 달리 기수 정렬은 두 수의 비교에 의해서 정렬이 이루어지지 않습니다.

정렬 방법은 먼저 0 에서 9 까지의 바구니를 준비 한 후

• 일의 자리 수를 기준으로 해당 바구니에 수를 넣습니다.그리고 수를 그대로 모읍니다.
• 다시 십의 자리수를 기준으로 해당 바구니에 수를 넣습니다.마찬가지로 수를 그대로 모읍니다.
• 다시 백의 자리수를 기준으로 ...

다음과 같은 수가 있다고 하면 (최대 자리수가 100 자리)

16,29,38,235,42,7,6,129,8,88,77,12,875,10

• 먼저 일의 자리를 봅니다. 16 은 6 번째 바구니에 , 29 는 9 번 바구니에 , 38 은 8 번 바구니에 .... 결과는 이렇게 됩니다..

  

  이 수를 차례대로 모읍니다.

  10 , 42 , 12 , 235 , 875 , 16 , 6 , 7 , 77 , 38 , 8 , 88 , 29 , 129

• 다시 10 의 자리를 기준으로 차례대로 바구니에 넣습니다.

  

  차례대로 모은 후

  6 , 7 , 8 , 10 , 12 , 16 , 29 , 129 , 235 , 38 , 42 , 875 , 77 , 88

• 100 의 자리를 기준으로 바구니에 넣은 후 모으면 정렬 완료

  

입력

• 입력으로 N가 K가 입력된다. (N<=5000, K<=100)
• 이후 N줄에 걸쳐서 데이터가 하나씩 입력된다. 데이터의 자릿수가 100 이하임은 보장된다.

출력

입출력 예

입력

10 2
35
3
66
530
1
29
601
6
984
8

출력

1
601
3
6
8
29
530
35
66
984

입출력 보충

출처:pl0892029