#include<stdio.h>
#include<string.h>
#define NUM 36


typedef struct card{
 char mark;
 int num;
}Card;


void swap(Card T[],int *a,int *b){
Card temp;

temp=T[*a];
T[*a]=T[*b];
T[*b]=temp;

}



void selesort(Card T[],int n){
int i,j,max,max_index;
Card temp;

 for(i=n-1;i>0;i--){
  max=T[0].num; max_index=0;
  for(j=1;j<=i;j++){ 
   if(T[j].num>=max){max=T[j].num; max_index=j;}
  }
  temp=T[max_index]; T[max_index]=T[i]; T[i]=temp;

}

}


void bubble(Card U[],int n){
 int k,l;
 Card temp;

for(k=0;k<n-1;k++){
 for(l=n-1;l>=k+1;l--){
  if(U[l].num<U[l-1].num){ temp=U[l]; U[l]=U[l-1]; U[l-1]=temp; }
 }
}

}


int stable(Card T[],Card U[],int n){
int i;
int count=0;
for(i=0;i<n;i++){
if( (T[i].num==U[i].num)&&(T[i].mark==U[i].mark) ){count++;}
}
if(count==n){return 1;}

}

int main(){
int n,i,x;
Card T[NUM];
Card U[NUM];
char a;
scanf("%d",&n);

for(i=0;i<n;i++){
 scanf(" %c%d",&T[i].mark,&T[i].num,&a);
 U[i]=T[i];
}


selesort(T,n);
bubble(U,n);

x=stable(T,U,n);



for(i=0;i<n-1;i++){
printf("%c%d ",U[i].mark,U[i].num);
}
printf("%c%d\n",U[n-1].mark,U[n-1].num);

printf("Stable\n");



for(i=0;i<n-1;i++){
printf("%c%d ",T[i].mark,T[i].num);
}
printf("%c%d\n",T[n-1].mark,T[n-1].num);



if(x==1){printf("Stable");}
else{printf("Not stable");}




return 0;
}