#include <stdio.h>

typedef struct{
  char suit;
  int value;
} Card;

int main()
{
  int i,j,num,min,cou,ju=0;
  Card C1[36],C2[36],tmp;

  scanf("%d",&num);

  for(i=0;i<num;i++){
    scanf(" %c%d",&C1[i].suit,&C1[i].value);
  }

  for(i=0;i<num;i++) C2[i]=C1[i];

    cou=1;
    while(cou){
      cou=0;
      for(j=num-1;j>=1;j--){
	if(C1[j].value < C1[j-1].value)
	  {
	    tmp=C1[j];
	    C1[j]=C1[j-1];
	    C1[j-1]=tmp;

	    cou=1;
	  }
      }
    }
    

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

    for(i=0;i<num-1;i++){
      min=i;
      
      for(j=i;j<num;j++){
	if(C2[j].value < C2[min].value) {
	  min=j;
	}
      }
      
      if(C2[i].value != C2[min].value){
	tmp=C2[i];
	C2[i]=C2[min];
	C2[min]=tmp;
      }
    }
  
  

   for(i=0;i<num-1;i++){
      printf("%c%d ",C2[i].suit,C2[i].value);
    }
    printf("%c%d\n",C2[i].suit,C2[i].value);
    
    for(i=0;i<num;i++){
      if(C1[i].value == C2[i].value && C1[i].suit != C2[i].suit){
	ju=1;
      }
    }
    if(ju==1){
      printf("Not stable\n");
    }
      else printf("Stable\n");
  
}