#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void wypisz (int * tab,int n)
{
    for (int i=0;i<n;i++)
        cout << tab[i] << " ";
    cout << endl;
}
void c_sort(int pom[][2],int n,int pos)
{
    int tmp[n][2];
    int val[n]={};
    for (int i=0;i<n;i++) val[pom[i][pos]]++;
    for (int i=1;i<n;i++) val[i]+=val[i-1];
    for (int i=n-1;i>=0;i--)
        {
            int j=--val[pom[i][pos]];
            tmp[j][0]=pom[i][0];
            tmp[j][1]=pom[i][1];
        }
    for (int i=0;i<n;i++)
        {
            pom[i][0]=tmp[i][0];
            pom[i][1]=tmp[i][1];
        }
}
void Radix(int * tab,int n)
{
    int pom[n][2];
    for (int i=0;i<n;i++)
    {
        pom[i][1]=tab[i]%n;
        pom[i][0]=tab[i]/n;
    }
    c_sort(pom,n,1);
    c_sort(pom,n,0);
    for (int i=0;i<n;i++)
        tab[i]=n*pom[i][0]+pom[i][1];
}
int main()
{
    int n;
    cin >> n;
    int tab[n];
    srand(time(NULL));
    for (int i=0;i<n;i++)
        tab[i]=rand()%(n*n);
    wypisz(tab,n);
    Radix(tab,n);
    wypisz(tab,n);
}