#include <bits/stdc++.h>
typedef struct {
  char a;
  int value;
} Card;
int main() {
  int i, j, n, min, flag = 0;
  Card c[36], b[36], n1, n2;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf(" %c%d", &c[i].a, &c[i].value);
    b[i].a = c[i].a;
    b[i].value = c[i].value;
  }
  for (i = 0; i < n - 1; i++) {
    for (j = n - 1; j > i; j--) {
      if (c[j].value < c[j - 1].value) {
        n1 = c[j];
        n2 = c[j - 1];
        c[j] = n2;
        c[j - 1] = n1;
      }
    }
  }
  for (i = 0; i < n; i++) {
    min = i;
    for (j = i; j < n; j++) {
      if (b[j].value < b[min].value) {
        min = j;
      }
    }
    n1 = b[i];
    n2 = b[min];
    b[i] = n2;
    b[min] = n1;
  }
  for (i = 0; i < n - 1; i++) {
    printf("%c%d ", c[i].a, c[i].value);
  }
  printf("%c%d\n", c[n - 1].a, c[n - 1].value);
  printf("Stable\n");
  for (i = 0; i < n - 1; i++) {
    printf("%c%d ", b[i].a, b[i].value);
  }
  printf("%c%d\n", b[n - 1].a, b[n - 1].value);
  for (i = 0; i <= n - 1; i++) {
    if (c[i].a != b[i].a) {
      flag = 1;
    }
  }
  if (flag == 1)
    printf("Not stable\n");
  else
    printf("Stable\n");
  return 0;
}
