#include<stdio.h>
#define MAX 36
#define True 1
#define False 0

typedef struct{
  char c;
  int num;
} card;

void cardsort(card []);
void select(card []);
int search(card [],card []); 

int number;

int main(){
  int i,j;
  card data[MAX];
  card data2[MAX];
  card in[MAX];
  card in2[MAX];
  
  
  scanf("%d",&number);
  for(i=0;i<number;i++) {
    scanf(" %c%d",&data[i].c,&data[i].num);
  }
  
  for(i=0;i<number;i++) {
    data2[i] = data[i];
    in[i] = data[i];
    in2[i] = data[i];
  }
  
  cardsort(data);
  select(data2);

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

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

  if(search(data,data2)==1) printf("Stable\n");
  else printf("Not Stable\n");
}


void cardsort (card n[]){
  int i,j,tmp;
  char tmpc;
  for(i=0;i<number;i++){
    for(j=number-1;j>i;j--){
      if(n[j].num<n[j-1].num){
	tmp=n[j].num;
	n[j].num=n[j-1].num;
	n[j-1].num=tmp;

	tmpc=n[j].c;
	n[j].c=n[j-1].c;
	n[j-1].c=tmpc;
      }
    }
  }
}


void select(card n[]){

  int min,i,j,tmp;
  for(i=0;i<number;i++){
    min=i;
    for(j=i;j<number;j++){
      if(n[j].num<n[min].num){
	min=j;
      }
    }
    if(min != i){
      tmp=n[i].num;
      n[i].num=n[min].num;
      n[min].num=tmp;
    }
  }
}

int search(card data[],card data2[]){
  int i,count=0;
    for(i=0;i<number;i++){
      if(data[i].c == data2[i].c && data[i].c == data2[i].c){
	count++;
      }
    }
  if(count==number) return True;
  else return False;
}