#include<stdio.h>
//1 行目　バブルソート
//2 安定かどうか
//3　選択ソート
//4 安定かどうか

 typedef struct{
  char mark;
  int number;
  int mark_number;
} card;
int n;
void bubblesort(card *);
void selectionsort(card*);
int main(){
  
  card A[36];
  int i,j,n;
  scanf("%d",&n);
  for(i=-0;i<36;i++){
    scanf("%c%d",&A[i].mark,&A[i].number);
    
    if(A[i].mark == 'D')A[i].mark_number = 4;
    if(A[i].mark == 'C')A[i].mark_number = 3;
    if(A[i].mark == 'H')A[i].mark_number = 2;
    if(A[i].mark == 'S')A[i].mark_number = 1;
    }

  bubblesort(A);
  selectionsort(A);
  return 0;
}

void bubblesort(card A[]){
  int minj;
  int i;
  card tmp;
  for(i=0;i<n-1;i++){
    if(A[i].number>A[i+1].number){
      
      tmp.number = A[i].number;
      A[i].number =A[i+1].number;
      A[i+1].number=tmp.number;

      
      tmp.mark = A[i].mark;
      A[i].mark =A[i+1].mark;
      A[i+1].mark=tmp.mark;
    }
    
    else if(A[i].number == A[i+1].number){
      //同じ番号でマークが異なる場合の処理

      
      if(A[i].mark_number > A[i+1].mark_number){
	   tmp.mark = A[i].mark; 
	  A[i].mark =A[i+1].mark;
	  A[i+1].mark=tmp.mark;
	}
	

	else continue;
    

	}
    
    
  } i=0;
while(i<n-1)printf("%c%d ",A[i].mark,A[i].number);
printf("%c%d ",A[n-1].mark,A[n-1].number);
    printf("\n");
    printf("Stable\n");

}


    
 void selectionsort(card A[]){
   int i,j,count =0;
  int minj;
  card tmp;
  for(i=0;i<n;i++){
	 minj = i ;
	
	for(j=i;j<n;j++){
  	if(A[j].number < A[minj].number)minj=j;
	}
	
	tmp.number = A[i].number;
	A[i].number = A[minj].number;
	A[minj].number =tmp.number;
	
	tmp.mark = A[i].mark;
	A[i].mark = A[minj].mark;
	A[minj].mark =tmp.mark;
  }i=0;
  while(i<n-1)printf("%c%d ",A[i].mark,A[i].number);
  printf("%c%d ",A[n-1].mark,A[n-1].number);
    printf("\n");
    
    i=0;
    while(i<n-1){if(A[i].mark_number <= A[i+1].mark_number) printf("Stable\n");
      else  count ++;
    }

    if(count >=1)printf("Not stable\n");
 }

