#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 36

typedef struct{
  char key[2];
  int value;
} SHCD;
int n;
int main(){
  SHCD C[N],temp,B[N];
  int i,j,a,b,minj,flag=0;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    scanf("%s",C[i].key);
    C[i].value = atoi(&C[i].key[1]);
    B[i] = C[i];  
}


  for(i = 0 ; i <= n-1 ; i++){
    for(j = n-1 ; j >= i+1 ; j--){
      if(C[j].value < C[j-1].value){
	temp = C[j];
	C[j] = C[j-1];
	C[j-1] = temp;
      }
    }
  }

  for(i = 0 ; i < n-1 ; i++){
    printf("%s ",C[i].key);
  }
  printf("%s\n",C[i].key);
  printf("Stable\n");




  for(i = 0 ; i < n ; i++){
    minj = i;
    for(j = i ; j < n ; j++){
      if(B[j].value < B[minj].value){
	minj = j; 
      } 
   
      }
   if( i != minj) {
	temp = B[minj];
	B[minj] = B[i];
	B[i] = temp;
    }
  }
  
  for(i = 0 ; i < n-1 ; i++){
    printf("%s ",B[i].key);
  }
  printf("%s\n",B[i].key);
 
  for( i = 0 ; i < n ; i++ )
    {
      if( strcmp(C[i].key,B[i].key) != 0 ){
	flag = 1;
      break;
      }
    } 
  if( flag == 0 ) printf("Stable\n");
 else printf("Not Stable\n");
  return 0;
}