#include <stdio.h>

void change(int n,int m,char s,char t)
{
 int l;
 char r;

 l=n;
 n=m;
 m=l;

 r=s;
 s=t;
 t=r;

}

void print(int a[],int N)
{
 int i;

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

}

struct card {
    char mark[1];
    int  num;
};

int main(void)
{
 int N,i,j,k,l,min;
 struct card a[36],b[36];

 scanf("%d",&N);

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

 for(i=0;i<N-1;i++){
  for(j=N-1;j<i+1;j--){
   if(a[j].num<a[j-1].num){
     change(a[j].num,a[j-1].num,a[j].mark,a[j-1].mark);
   }
  }
 }

 for(i=0;i<N;i++){
  b[i]=a[i];
 }

 print(a,N);
 printf("Stable\n");

 for(i=0;i<N-1;i++){

  min=i;
  for(j=i;j<N;j++){

   if(a[j]<a[min]){
    min=j;
   }
   change(a[i].num,a[min].num,a[i].mark,a[min].mark);

  }
 }

 print(a,N);
 for(i=0;i<N;i++){
  if(a[i].num==b[i].num&&a[i].mark!=b[i]){
   printf("Not stable\n");
  }else{
   printf("Stable\n");
  }
 }

 return 0;

}