#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main(){
  int flag=1,i,j,N,swap,minj;

  //scanf N
  scanf("%d",&N);

  //making array
  char A_in_sig[N], A_out_b_sig[N], A_out_s_sig[N];
  int A_in_val[N], A_out_b_val[N], A_out_s_val[N];
  
  //fill A_in[]
  for(i=0;i<N;i++){ //?¢??????°???N2???????????????????????\??????????????°???N2-1(????????????????????????????????§???????????????)
    scanf(" %c%d",&A_in_sig[i],&A_in_val[i]); //getc???????????°"????????????????????????"????????¨
  }
  
  //copying A_in_val[] to each output Arrays
  for(i=0;i<N;i++){
//    printf("%d: %c\n",i,A_in_val[i]);
    A_out_b_val[i] = A_in_val[i];
    A_out_b_sig[i] = A_in_sig[i];
    A_out_s_val[i] = A_in_val[i];
    A_out_s_sig[i] = A_in_sig[i];
  }

  

  //BUBBLE SORT
  i=0;
  while(flag){
    flag = 0;
    for(j=N-1;j>i;j--){ //???????????????????????°??????????????????????????????
      if(A_out_b_val[j]<A_out_b_val[j-1]){
        //int
        swap = A_out_b_val[j];
        A_out_b_val[j] = A_out_b_val[j-1];
        A_out_b_val[j-1] = swap;
        //char
        swap = A_out_b_sig[j];
        A_out_b_sig[j] = A_out_b_sig[j-1];
        A_out_b_sig[j-1] = swap;
        flag = 1; //to be continue
      }
    }
    i++;
  }

  //print Array
  for(i=0;i<N;i++){
    printf("%c%d", A_out_b_sig[i],A_out_b_val[i]);
    if(i<N-1){ //?????????????????????????????????
      printf(" ");
    }
  }
  printf("\n");
  //print Stablily 
  printf("Stable\n"); //always 'Stable'
  
  
  //SELECTION SORT
  for(i=0;i<N-1;i++){ //1??????(??????)????£???°??????2??????????????????????????????????????§
    minj = i; //first
    for(j=i;j<N;j++){
      if(A_out_s_val[j]<A_out_s_val[minj]){ //update minj
        minj = j;
      }
    }
    //changing
    if(minj != i) {
      //int
      swap = A_out_s_val[i];
      A_out_s_val[i] = A_out_s_val[minj];
      A_out_s_val[minj] = swap;
      //char
      swap = A_out_s_sig[i-1];
      A_out_s_sig[i-1] = A_out_s_sig[minj-1];
      A_out_s_sig[minj-1] = swap;
    }
  }

  //print Array
  for(i=0;i<N;i++){
    printf("%c%d", A_out_b_sig[i],A_out_b_val[i]);
    if(i<N-1){ //?????????????????????????????????
      printf(" ");
    }
  }
  printf("\n");
  
  //print Stablity
  if(strcmp(A_out_b_sig, A_out_s_sig) == 0){
    printf("Stable\n");
  }else{
    printf("Not stable\n");
  }

  return 0;
}