음이 아닌 정수로 이루어진 배열이 주어진다. 다음 의사 코드에 따라 기수 정렬을 수행하고, 각 단계가 끝난 뒤의 배열을 출력해 보자.

이 문제에서는 십진수의 낮은 자릿수부터 차례대로 정렬하는 기수 정렬을 사용한다. 먼저 일의 자리를 기준으로 정렬하고, 이후 십의 자리, 백의 자리 순서로 정렬한다.

현재 확인하는 자릿수의 값이 같은 원소들은 정렬하기 전의 순서를 유지해야 한다. 해당 자릿수가 없는 수의 자릿값은 \(0\)으로 취급한다.

의사 코드

M = 배열 A의 최댓값
place = 1

반복
    0번부터 9번까지 번호가 붙은 빈 보관함을 만든다.

    for i = 1부터 N까지
        digit = (A[i] / place의 몫) % 10
        digit번 보관함의 뒤에 A[i]를 넣는다.

    index = 1
    for digit = 0부터 9까지
        digit번 보관함의 원소를 앞에서부터 하나씩 꺼낸다.
        꺼낸 원소를 차례대로 A[index]에 저장하고 index를 1씩 증가시킨다.

    배열 A의 모든 원소를 출력한다.

    if M / place의 몫 < 10
        반복을 종료한다.

    place = place * 10

의사 코드에서 한 자릿수를 기준으로 배열 전체를 정렬하는 과정을 한 단계라고 한다. 배열의 최댓값이 가진 가장 높은 자릿수까지 모든 단계를 수행한다.

배열의 최댓값이 \(0\)이면 일의 자리를 기준으로 한 단계를 한 번 수행하고 배열을 출력한다.

입력

첫째 줄에 배열의 크기 \(N\)이 주어진다.

둘째 줄에 배열의 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

출력

각 단계가 끝날 때마다 배열의 모든 원소를 공백으로 구분하여 한 줄에 출력한다.

제한 사항

• \(2 \le N \le 100\)
• \(0 \le A_i \le 1,000,000,000\)

예제 입력 1

8
170 45 75 90 802 24 2 66

예제 출력 1

170 90 802 2 24 45 75 66
802 2 24 45 66 170 75 90
2 24 45 66 75 90 170 802

예제 설명 1

배열의 최댓값은 \(802\)이므로 일의 자리, 십의 자리, 백의 자리까지 총 세 단계를 수행한다. 각 단계에서는 같은 자릿값을 가진 원소들의 기존 순서를 유지한다.