#include<stdio.h>
#define N 36
  
typedef struct{
  char a;
  int b;
}card;
  
int main(){
  
  int n,min,i,j;
  card Hira[N],d[N],s;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c%d",&Hira[i].a,&Hira[i].b);
    d[i]=Hira[i];
  }
  
  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      if(Hira[j].b<Hira[j-1].b){
    s=Hira[j];
    Hira[j]=Hira[j-1];
    Hira[j-1]=s;
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%c%d ",Hira[i].a,Hira[i].b);
    if(i == n-1) break;
    printf(" ");
  }
  printf("\nStable\n");
  
  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(d[j].b<d[min].b){ 
    min=j;
      }    
    }
    if(i!=min){
      s=d[i];
      d[i]=d[min];
      d[min]=s;
    }
  }
  
  for(i=0;i<n;i++){
    printf("%c%d ",d[i].a,d[i].b);
    if(i == n-1) break;
    printf(" ");
  }
  for(i=0;i<n;i++){
    if(Hira[i].a!=d[i].a){ 
      j=0; break;
    }
    else if(Hira[i].a==d[i].a) j=1;
  }
  if(j==0)  printf("Not stable\n");
  else if(j==1)  printf("Stable\n");
  return 0;
}