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

typedef struct tuple{
  char suit;
  int value;
}Card;

void swap(int *p1, int *p2){
  int tmp;

  tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;

}

void swap_char(char *p1, char *p2){
  char tmpc;

  tmpc = *p1;
  *p1 = *p2;
  *p2 = tmpc;

}

int isStable(Card *p1, Card *p2, int n){
  int i;

  for(i=0; i<n; i++){
    if(p1[i].value == p2[i].value){
      if(p1[i].suit != p2[i].suit) return 0;
    }
  }

  return 1;
}

int main(){
  int n,i,j,min;
  int frag;
  Card *deck1,*deck2;

  // input and allocation
  scanf("%1d",&n);
  getchar();


  deck1 = (Card *)malloc(sizeof(Card) * n);
  deck2 = (Card *)malloc(sizeof(Card) * n);
  for(i=0; i<n; i++){
    scanf("%c%d%*c", &deck1[i].suit, &deck1[i].value);
    printf("test i = %d %c %d\n", i, deck1[i].suit, deck1[i].value);
    deck2[i].suit = deck1[i].suit;
    deck2[i].value = deck1[i].value;
  }
  
  // bubble sort
  for(i=0; i<n; i++){
    for(j=n-1; j>i; j--){
      if(deck1[j].value < deck1[j-1].value){
	swap(&deck1[j].value, &deck1[j-1].value);
	swap_char(&deck1[j].suit, &deck1[j-1].suit);
      }
    }
  }
 
  // selection sort
  for(i=0; i<n; i++){
    min = i;
    for(j=i; j<n; j++){
      if(deck2[j].value < deck2[min].value) min = j;
    }
    swap(&deck2[i].value, &deck2[min].value);
    swap_char(&deck2[i].suit, &deck2[min].suit);
  }
 
  // check stable
  frag = isStable(deck1,deck2,n);

  // first output
  for(i=0; i<n; i++){
    printf("%c%d",deck1[i].suit,deck1[i].value);
    if(i == n-1) continue;
    printf(" ");
  }
  printf("\nStable\n");

  // second output
  for(i=0; i<n; i++){
    printf("%c%d",deck2[i].suit,deck2[i].value);
    if(i == n-1) continue;
    printf(" ");
  }
  switch(frag){
  case 1:
    printf("\nStable\n");
    break;
  case 0:
    printf("\nNot Stable\n");
    break;
  }
 
  free(deck1);
  free(deck2);
 
  return 0;
}