#include <stdio.h>

struct Card {char suit,value;};

void swap(int a,int b){
  int t=a;
  a=b;
  b=t;
}

void bubbleSort(struct Card C[],int N){
  int i,j;
  for(i=0;i<N;i++){
    for(j=N-1;j>=i+1;j--){
      if(C[j].value,C[j-1].value){
        swap(C[j].value,C[j-1].value);
      }
    }
  }
}

void selectionSort(struct Card C[],int N){
  int i,j,minj;
  for(i=0;i<N;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(C[minj].value>C[j].value){
        minj=j;
      }
      swap(C[minj].value,C[i].value);
    }
  }
}

void print(struct Card C[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%c%c",C[i].suit,C[i].value);
  }
  printf("\n");
}

int isStable(struct Card S1[],struct Card S2[],int N){
  int i;
  for(i=0;i<N;i++){
    if(S1[i].suit!=S2[i].suit) return 0;
  }
  return 1;
}

int main(void){
  int n,i;
  scanf("%d",&n);
  struct Card C1[n],C2[n];
  char ch;
for(i=0;i<n;i++){
  scanf("%c %c",C1[i].suit,C1[i].value);
}

for(i=0;i<n;i++){
  C2[i]=C1[i];
}

bubbleSort(C1,n);
selectionSort(C2,n);

print(C1,n);
if(isStable(C1,C2,n)==1){
  printf("Stable");
}

else{
  printf("Not stable");
}

print(C2,n);
if(isStable(C1,C2,n)==1){
  printf("Stable");
}


else{
  printf("Not stable");
}

  return 0;
}