#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
void scalanie(int tab[],int p,int k)
{
	int tab2[k];
	cout<<endl;
	for(int i=p;i<k;i++)
	{
		tab2[i]=tab[i];
	}
	cout<<endl;
	int s=(k+p)/2;
	int l=p,r=s,z=p;
	while((l<s)&&(r<k))
	{
		if(tab2[l]<tab2[r])	tab[z++]=tab2[l++];
		else tab[z++]=tab2[r++];
	}
	while(l<s)tab[z++]=tab2[l++];
	while(r<k)tab[z++]=tab2[r++];
}
void sortowanie(int tab[],int p,int k)
{
	int c;
	c=(k+p)/2;
	if(p<k)
	{
	sortowanie(tab,p,c);
	sortowanie(tab,c+1,k);
	scalanie(tab,p,k);
	}
}
int main()
{
	srand(time(NULL));
	int x;
	cin>>x;
	int tab[x];
	for(int i=0;i<x;i++)
	{
		tab[i]=rand()%10;

	}
	for(int i=0;i<x;i++)
	{
		cout<<tab[i]<<" ";
	}
	sortowanie(tab,0,x);
	cout<<endl;
	for(int i=0;i<x;i++)
	{
		cout<<tab[i]<<" ";
	}
	return 0;
}