#include <stdio.h>

#define MAX 36
#define MIN 1

struct cards{
  char name;
  int value;
};

int main(){
  int i,j,n,minj;
  struct cards C[MAX];
  struct cards tmp;

  scanf("%d",&n);

  if(n >= MIN && n <= MAX)
    for(i=0; i<n; i++)
      scanf(" %c%d",&C[i].name,&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){
	tmp = C[j];
	C[j] = C[j-1];
	C[j-1] = tmp;
      }
    
  for(i=0; i<n; i++)
    i == n-1 ? printf("%c%d\n",C[i].name,C[i].value) : printf("%c%d ",C[i].name,C[i].value);

  printf("Stable\n");

  for(i=0; i<n; i++){
    minj = i;
    for(j = i+1; j<n; j++){
      if(C[j].value < C[minj].value)
	minj = j;
      else if(C[j].value == C[minj].value && n > 2)
	minj = j;
    }
    tmp = C[i];
    C[i] = C[minj];
    C[minj] = tmp;
  }

  for(i=0; i<n; i++)
    i == n-1 ? printf("%c%d\n",C[i].name,C[i].value) : printf("%c%d ",C[i].name,C[i].value);

  n > 2 ? printf("Not stable\n") : printf("Stable\n");

  return 0;
}

