#include<stdio.h>
 
struct Card{
  char suit;
  char value;
};
 
 
void BubbleSort(struct Card *A, int length) {
 
  int i, j;
  char tmp;
  char tmp1;
 
  for(i = 0; i < length; i++) {
    for(j = length-1; j > i; j--) {
      if(A[j].value < A[j-1].value) {
 
    tmp = A[j].value;
    tmp1 = A[j].suit;
 
    A[j].value = A[j-1].value;
    A[j].suit = A[j-1].suit;
 
    A[j-1].value = tmp;
    A[j-1].suit = tmp1;
 
      }
    }
  }
}
 
void SelectionSort(struct Card *A,int length) {
 
  int i, j, mini;
  char tmp;
  char tmp1;
 
  for(i = 0; i < length; i++) {
    mini = i;
    for(j = i; j < length; j++) {
      if(A[j].value < A[mini].value) {
    mini = j;
      }
    }
    if(i != mini) {
    tmp = A[i].value;
    tmp1 = A[i].suit;
 
    A[i].value = A[mini].value;
    A[i].suit = A[mini].suit;
 
    A[mini].value = tmp;
    A[mini].suit = tmp1;
 
    }
  }
}
 
 
 
int main(){
  struct Card card1[101], card2[101];
  char table[9][4]={};
  int cnt[9]={};
 
  int n, i,j,flg=0;
  char ch;
 
  scanf("%d%c", &n, &ch);
  for ( i = 0; i < n; i++ ){
    scanf("%c%c%c", &card1[i].suit, &card1[i].value, &ch);
    table[card1[i].value-'1'][cnt[card1[i].value-'1']]=card1[i].suit;
    cnt[card1[i].value-'1']++;
  }
  for(i = 0; i < n; i++) {
 
    card2[i].suit = card1[i].suit;
    card2[i].value = card1[i].value;
  }
 
  BubbleSort(C1, n);
  SelectionSort(C2, n);
 
 
  for(i=0;i<9;i++)cnt[i]=0;
 
  if(table[card1[0].value-'1'][cnt[card1[0].value-'1']++]!=card1[0].suit)
    {
      flg=1;
    }
  printf("%c%c", card1[0].suit, card1[0].value);
  for(i = 1; i < n; i++) {
  if(table[card1[i].value-'1'][cnt[card1[i].value-'1']++]!=card1[i].suit)
    {
      flg=1;
    }
  printf(" %c%c?\n", card1[i].suit, card1[i].value);
  }
 
  if(flg==0)
    printf("Stable\n");
  else
    printf("Not stable\n");
 
  for(i=0;i<9;i++)cnt[i]=0;
  flg=0;
 
  if(table[card2[0].value-'1'][cnt[card2[0].value-'1']++]!=card2[0].suit)
    {
      flg=1;
    }
 
 
 printf("%c%c", card2[0].suit, card2[0].value);
  for(i = 1; i < n; i++) {
  if(table[card1[i].value-'1'][cnt[C1[i].value-'1']++]!=card2[i].suit)
    {
      flg=1;
    }
  printf(" %c%c", card2[i].suit, card2[i].value);
  }
 
  if(flg==0)
    printf("\nStable\n");
  else
    printf("\nNot stable\n");
 
  return 0;
}