#include<stdio.h>

struct Card{
  char suit;
  int value;
};

int main(){
  struct Card C1[101], C2[101],a,b;
  int N, i,j;
  int minj;
  char ch;
  
  scanf("%d%c", &N, &ch);
  for ( i = 1; i <= N; i++ ){
    scanf("%c%d%c", &C1[i].suit, &C1[i].value, &ch);
    C2[i]=C1[i];
  }

  //以下Bubble Sort
   for(i=1;i<N;i++){
    for(j=N;j>i;j--){
      if(C1[j].value<C1[j-1].value){
        a=C1[j];
	C1[j]=C1[j-1];
	C1[j-1]=a;
      }
    }
  }

   //以下Selection Sort
   for(i=1;i<N-1;i++){
     minj = i;
     for(j=i;j<=N;j++){
       if(C2[j].value<C2[minj].value){
	 minj = j;
       }
     }
     b=C2[i];
     C2[i]=C2[minj];
     C2[minj]=b; 
   }

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

   int flag=1;   
   for(i=1;i<=N;i++){
     if(C1[i].suit==C2[i].suit&&C1[i].value==C2[i].value){
     } else { flag=0;
     }  
   }
   if(flag==1){
     printf("Stable\n");
   } else { printf("Not stable\n");
   }

   return 0;
}