#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int a[100];
int temp[100];
void slivaem(int l,int c,int r)
{
    int n1=l,n2=c+1,n3=0,i;
    while(n1<=c && n2<=r)
    {
        if(a[n1]<a[n2]) {temp[n3]=a[n1]; n3++; n1++;}
        else
        {
            temp[n3]=a[n2];
            n3++;
            n2++;
        }

    }
    while(n1<=c)
    {
        temp[n3]=a[n1]; n3++; n1++;
    }
    while(n2<=r)
    {
        temp[n3]=a[n2]; n3++; n2++;
    }

    int j=0;
    for(i=l;i<=r;i++)
    {
        a[i]=temp[j];
        j++;
    }




}
void sortsl(int n1,int n2)
{
    if (n1>=n2) {return;}
    int c;
    c=(n1+n2)/2;
    sortsl(n1,c);
    sortsl(c+1,n2);
    slivaem(n1,c,n2);
    for(int i=0;i<n;i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
}

int main()
{
    int i;

    cin >> n;
    srand(time(0));

    for(i=0;i<n;i++)
    {
        a[i] = rand() %100;

    }


    sortsl(0,n-1);
    for(i=0;i<n;i++)
    {
        cout << a[i] << " ";

    }
    return 0;
}