#include<stdio.h>

struct card{
  char design[100];
  int num;
};

void bubble(struct card a[], int N){
  int i, j, temp;
  int flag = 1;
  char *t;
  for (i=0; flag==1; i++) {
    flag = 0;
    for (j=N-1; j>=i+1; j--) {
      if (a[j-1].num > a[j].num) {
        temp       = a[j-1].num; 
        a[j-1].num = a[j].num;
        a[j].num   = temp;
        *t            = a[j-1].design;
        a[j-1].design = a[j].design;
        a[j].design   = *t;
        flag = 1;
      }
    }
  }
}
void selection(struct card a[], int N){
  int i, j, temp, minj;
  char t;
  for (i=0; i<N; i++) {
    minj = i;
    for (j=i; j<N; j++) {
      if (a[j].num < a[minj].num)
        minj = j;
    }
    temp       = a[j-1].num;
    a[j-1].num = a[j].num;
    a[j].num   = temp;
    t             = a[j-1].design;
    a[j-1].design = a[j].design;
    a[j].design   = t;
  }
}
void print(struct card a[], int N){
  int i;
  for (i=0; i<N; i++) {
    if (i>0)
      putchar(' ');
    printf("%c%d", a[i].design, a[i].num);
  }
  printf("\n");
}
int stable(struct card c1[], struct card c2[], int N){
  int i;
  for (i=0; i<N; i++) {
    if (c1[i].design != c2[i].design)
      return 0;
  }
  return 1;
}

int main(){
  struct card c1[100], c2[100];
  int N, i;

  scanf("%d", &N);
  for (i=0; i<N; i++)
    scanf("%c%d", &c1[i].design, &c1[i].num);

  for (i=0; i<N; i++) {
    c2[i].design = c1[i].design;
    c2[i].num    = c1[i].num;
  }

  bubble(c1, N);
  selection(c2, N);

  print(c1, N);
  printf("Stable\n");
  print(c2, N);
  if (stable(c1, c2, N)==1) {
    printf("Stable\n");
  } else {
    printf("Not stable\n");
  }
  return 0;
}