#include <stdio.h>

struct Card{ char suit, value;};

int bubble(Card a[],int N){
  int i,j,z;
  z=0;
  for(i=0;i<N;i++){
    for(j=N-1;j>=i+1;j--){
      if(a[j].value<a[j-1].value){
        Card 
        z=a[j-1];
        a[j-1]=a[j];
        a[j]=z;
      }
    }
  }
}

int select(struct Card a[],int N){
  int i,j,s,z,minj;
  z=0;
  for(i=0;i<N-1;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(a[j].value<a[minj].value){
        minj=j;
      }
    }
    Card z=b[i];
    b[i]=b[minj];
    b[minj]=z;
  }
}

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

int isStable(struct Card C1[],struct Card C2[],int N){
  int i,j,x,y,flag;
  flag=1;
  for(i=0;flag;i++){
      flag=0;
      for(j=i+1;j<N-1;j++){
        for(x=0;x<N-1;x++){
          for(y=x+1;y<N-1;y++){
            if(C1[i].suit==C1[j].suit&&C1[i].suit==C2[y].suit&&C1[j].suit==C2[x].suit){
              printf("Stable\n");
              flag=1;
            }
          }
        }
      }
  printf("Not stable\n");
  }
}

int main(void)
{
  Card C1[100],C2[100];
  int N;
  char ch;

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&a[i].suit);
    scanf("%d",&a[i].value);
    }
  for(i=0;i<N;i++){
    C2[i]=C1[i];
  }
  bubble(C1,N);
  select(C2,N);

  print(C1,N);
  printf("Stable\n");
  print(C2,N);
  if(isStable(C1,C2,N)){
    printf("Stable\n");
    }
  else{
    printf("Not stable\n");
  }
  return 0;
}