#include <string.h>
#include <stdio.h>

 struct card {
     char mark;
     int  num;
 };

 int main(void)
 {
  int N,i,j,s,min,x;
  char *t="A";
  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){
      s=a[j].num;
      a[j].num=a[j-1].num;
      a[j-1].num=s;
      strcpy(t,a[j].mark);
      strcpy(a[j].mark,a[j-1].mark);
      strcpy(a[j-1].mark,t);
    }
   }
  }

  for(i=0;i<N;i++){
   b[i]=a[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);
  printf("Stable\n");

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

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

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

   }
  }

  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);

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

  return 0;

 }