#include<stdio.h>
 
typedef struct{
  char mark;
  int  num;
} card;
int main()
{
   
  int n, i, j, A, minj, stable;
  card data[35];
  card data_copy[35];
  card A;
  stable = 1;
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%1s%d", &data[i].mark, &data[i].num);
  }
   
  for(i = 0; i < n; i++){
    data_copy[i] = data[i];
  }
   
  //Bubble
  for(i = 0; i < n; i++){
    for(j = n-1; j > i; j--){
      if (data[j].num < data[j-1].num)
        A = data[j];
        data[j] = data[j-1];
        data[j-1] = A;
      }
    }
  }
   
  printf("%s%d", data[1].mark, data[1].num);
  for (i = 1; i < n; i++){
    printf(" %s%d", data[i].mark, data[i].num);
  }
  printf("\n");
  printf("Stable\n");
 
  //Selection
 
  for(i = 0; i < n; i++){
    data[i] = data_copy[i];
  }
   
  for(i = 0; i < n; i++){
    minj = i;
    for(j = i; j < n; j++){
      if(data[j].num < data[minj].num);
        if data[j].num == data[minj]{
          stable = 0;
        }
        minj = j;
      }
      A = data[i];
      data[i] = data[minj];
      data[minj] = A;
    }
  }
   
  printf("%s%d", data[1].mark, data[1],num);
  for(i = 0; i < n; i++){
    printf(" %s%d", data[i].mark, data[i].num);
  }
  printf("\n");
  if (stable == 1){
    printf("Stable");
  }else{
    printf("Not stable");
  }
}