#include<stdio.h>

typedef struct{
  int value;
  char moji;
}Set;

void BubbleSort(void);
void SelectionSort(void);
void isstable(int);

int n;
Set A[36],B[36];

int main(){
  //Set A[36],B[36];
  int i;

  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf(" %c%d",&A[i].moji,&A[i].value);
    //printf("%c\n", A[i].moji);
    B[i]=A[i];
  }
//for(i=0;i<n;i++)printf("%c%d\n", A[i].moji,A[i].value);
  BubbleSort();

  SelectionSort();

  return 0;
}

void BubbleSort(){
  int i,j,x=0;
  Set c;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(A[j].value<A[j-1].value){
        c = A[j];
        A[j] = A[j-1];
        A[j-1] = c;
      }
    }
  }
  for(i=0;i<n-1;i++){
    printf("%c%d ", A[i].moji,A[i].value);
    if(A[i].moji>A[i+1].moji && A[i].value==A[i+1].value)x=1;
  }
  printf("%c%d\n", A[i].moji,A[i].value);
  isstable(x);
}

void SelectionSort(){
  int i,j,x,min;
  Set c;

  for(i=0;i<n;i++){
    min = i;
    for(j=i;j<n;j++){
      if(B[j].value<B[min].value) min = j;
    }
    c = B[i];
    B[i] = B[min];
    B[min] = c;
  }
  for(i=0;i<n-1;i++){
    printf("%c%d ", B[i].moji,B[i].value);
    if(B[i].moji>B[i+1].moji && B[i].value==B[i+1].value)x=1;
  }
  printf("%c%d\n", B[i].moji,B[i].value);
  isstable(x);
}

void isstable(int x){
  if(x) printf("Not stable\n");
  else printf("Stable\n");
}