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

버블 정렬은 서로 이웃한 두 수를 차례대로 비교한다. 왼쪽 수가 오른쪽 수보다 크면 두 수의 위치를 바꾼다. 한 단계가 끝나면 아직 정렬되지 않은 부분에서 가장 큰 수가 그 부분의 맨 오른쪽으로 이동한다.

의사 코드

for i = 1부터 N - 1까지
    for j = 1부터 N - i까지
        if A[j] > A[j + 1]
            A[j]와 A[j + 1]을 교환한다.
    배열 A의 모든 원소를 출력한다.

의사 코드의 바깥쪽 반복 한 번을 한 단계라고 한다. 배열이 도중에 이미 정렬되었더라도 반복을 중단하지 않고, 반드시 \(N-1\)단계를 모두 수행해야 한다.

입력

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

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

출력

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

총 \(N-1\)개의 줄을 출력해야 한다.

제한 사항

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

예제 입력 1

5
5 3 2 4 1

예제 출력 1

3 2 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

예제 설명 1

첫 번째 단계에서는 이웃한 두 수를 차례대로 비교하고 교환하여 가장 큰 수 \(5\)를 배열의 맨 오른쪽으로 이동시킨다. 같은 과정을 남은 부분에 반복하면 네 번째 단계가 끝난 뒤 배열 전체가 오름차순으로 정렬된다.