#include<stdio.h>
#define MAX 36
struct Card{
  char suit;
  int value;
};
int main()
{
  struct Card a1[MAX],a2[MAX],tmp;
  int i,j,tmp2;
  int min,x,kt=1;
  char y,tmp1;
  scanf("%d",&x);
  scanf("%c",&y);
  for(i=0;i<x;i++)
    {
      scanf("%c%d",&a1[i].suit,&a1[i].value);
      scanf("%c",&y);
      a2[i] = a1[i];
    }
  //ここからがb
  for(i=0;i<x;i++)
    {
      for(j=x-1;j>i+1;j--)
	{
	  if(a1[j].value < a1[j-1].value)
	    {
	      // tmp1 = a1[j].suit;
	      // tmp2 = a1[j].value;
	      tmp = a1[j];
	      a1[j] = a1[j-1];
	      //  a1[j-1].suit = tmp1;
	      // a1[j-1].value = tmp2;
	      a1[j-1] = tmp;
	    }
	}
    }
  //ここからがi
  for(i=0;i<x;i++)
    {
      min = i;
      for(j=i;j<x;j++)
	{
	  if(a2[j].value < a2[min].value)
	    {
	      min = j;
	    }
	}
      if(i!=min)
	{
	  // tmp1 = a2[i].suit;
	  // tmp2 = a2[i].value;
	  tmp = a2[i];
	  a2[i].suit = a2[min].suit;
	  a2[i].value = a2[min].value;
	  // a2[min].suit = tmp1;
	  // a2[min].value = tmp2;
	  a2[min] = tmp;
	}
    }
  for(i=0;i<x;i++)
    {
      printf("%c%d",a1[i].suit,a1[i].value);
      if(i != x-1)
	{
	  printf(" ");
	}
      else printf("\n");
    }
  printf("Stable\n");
 for(i=0;i<x;i++)
    {
      printf("%c%d",a2[i].suit,a2[i].value);
      if(i != x-1)
	{
	  printf(" ");
	}
      else printf("\n");
    }
 for(i=0;i<x;i++)
   {
     if(a1[i].suit != a2[i].suit)
       {
	 printf("Not Stable\n");
	 kt = 0;
	 break;
       }
   }
 if(kt==1)
   {
     printf("Stable\n");
   }
 return 0;
}