#include<stdio.h>

void bubblesort(char*,int*,int);
void selectionsort(char*,int*,int);
int isStable(char*,int*,char*,int*,int);

int main(void)
{
int N,i;
scanf("%d\n",&N);
int number[N];
char suit[N];
for(i=0;i<N;i++) scanf("%c%d ",&suit[i],&number[i]);
bubblesort(suit,number,N);
selectionsort(suit,number,N);
return 0;
}

void selectionsort(char *tagin,int *arrayin,int N)
{
int i,mini,j,a,arrayout[N];
char tagout[N],tagA;
memcpy(tagout,tagin,sizeof(tagin));
memcpy(arrayout,arrayin,sizeof(arrayin));
for(i=0;i<N-1;i++)
{
mini=i;
for(j=i+1;j<N;j++)
{
if(arrayout[j]<arrayout[mini]) mini=j;
}
a=arrayout[i],tagA=tagout[i];
arrayout[i]=arrayout[mini],tagout[i]=tagout[mini];
arrayout[mini]=a,tagout[mini]=tagout[i];
}
for(i=0;i<N-1;i++) printf("%c%d ",tagout[i],arrayout[i]);
printf("%c%d\n",tagout[N-1],arrayout[N-1]);
if(isStable(tagin,arrayin,tagout,arrayout,N)==1) printf("Stable\n");
else printf("not Stable\n");
}

void bubblesort(char *tagin,int *arrayin,int N)
{
int i=0,j,flag=1,a,arrayout[N];
char tagout[N],tagA;
memcpy(tagout,tagin,sizeof(tagin));
memcpy(arrayout,arrayin,sizeof(arrayin));
while(flag)
{
flag=0;
for(j=N-1;j>i;j--)
{
if(arrayout[j]<arrayout[j-1])
{
a=arrayout[j],tagA=tagout[j];
arrayout[j]=arrayout[j-1],tagout[j]=tagout[j-1];
arrayout[j-1]=a,tagout[j-1]=tagA;
flag=1;
}
}
i++;
}
for(i=0;i<N-1;i++) printf("%c%d ",tagout[i],arrayout[i]);
printf("%c%d\n",tagout[N-1],arrayout[N-1]);
if(isStable(tagin,arrayin,tagout,arrayout,N)==1) printf("Stable\n");
else printf("not Stable\n");
}

int isStable(char *tagin,int *numberin,char *tagout,int *numberout,int N)
{
int i,j,a,b;
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
for(a=0;a<N;a++)
{
for(b=a+1;b<N;b++)
{
if(numberin[i]==numberin[j] && numberin[i]==numberout[b] && tagin[i]==tagin[b] && numberin[j]==numberout[a] && tagin[j]==tagin[a]) return 0;
}
}
}
}
return 1;
}