include<stdio.h>
#define N 36
  
typedef struct{
  char a;
  int b;
}Card;
  
int main(){
  
  int n,min,i,j;
  Card A1[N],A2[N],a;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c%d",&A1[i].a,&A1[i].b);
    A2[i]=A1[i];
  }
  
  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      if(A1[j].b<A1[j-1].b){
    a=A1[j];
    A1[j]=A1[j-1];
    A1[j-1]=a;
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%c%d",A1[i].a,A1[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(A2[j].b<A2[min].b){ 
    min=j;
      }    
    }
    if(i!=min){
      a=A2[i];
      A2[i]=A2[min];
      A2[min]=a;
    }
  }
  
  for(i=0;i<n;i++){
    printf("%c%d",A2[i].a,A2[i].b);
    if(i == n-1) break;
    printf(" ");
  }
  for(i=0;i<n;i++){
    if(A1[i].a!=A2[i].a){ 
      j=0; break;
    }
    else if(A1[i].a==A2[i].a) j=1;
  }
  if(j==0)  printf("\nNot stable\n");
  else if(j==1)  printf("\nStable\n");
  return 0;
}