#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void BubbleSort(char **A,int n)
{
  int i,j;
  int buf[3];
  int count=0;
  for(i=0;i<n;i++)
    {
      for(j=n-1;j>i;j--)
        {
          if(A[j-1][1]>A[j][1])
            {
              strcpy(buf,A[j-1]);
              strcpy(A[j-1],A[j]);
              strcpy(A[j],buf);
            }
        }
    }
  printf("%s",A[0]);
  for(i=1;i<n;i++)
    {
      printf(" %s",A[i]);
    }
  printf("\n");
  if(count)
    {
      printf("Not stable\n");
    }
  else
    {
      printf("Stable\n");
    }
}
void SelectionSort(char **A,int n)
{
  int i,j;
  int min;
  char buf[3];
  int count=0;

  for(i=0;i<n;i++)
    {
      min=i;
      for(j=i;j<n;j++)
        {
          if(A[j][1]<A[min][1])
            {
              min=j;
            }
        }
      if(i!=min)
        {
          strcpy(buf,A[i]);
          strcpy(A[i],A[min]);
          strcpy(A[min],buf);
        }
    }
  printf("%s",A[0]);
  for(i=1;i<n;i++)
    {
      printf(" %s",A[i]);
    }
  printf("\n");
  if(count)
    {
      printf("Not stable\n");
    }
  else
    {
      printf("Stable\n");
    }
}
int main()
{
  int n;
  char **card1;
  char **card2;
  int i;
  scanf("%d",&n);
  card1=(char**)malloc(sizeof(char*)*n);
  card2=(char**)malloc(sizeof(char*)*n);
  for(i=0;i<n;i++)
    {
      card1[i]=(char*)malloc(sizeof(char)*3);
      card2[i]=(char*)malloc(sizeof(char)*3);
      scanf("%s",card1[i]);
      strcpy(card2[i],card1[i]);
    }
  BubbleSort(card1,n);
  SelectionSort(card2,n);
  return 0;
}
