#include<stdio.h>

#define N 36

typedef struct{
  char suit;
  int value;
} Card;

int main()
{
  int i,j,n,min,flag=0;
  Card a[N],b[N],a1,a2;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf(" %c%d",&a[i].suit,&a[i].value);
      b[i].suit=a[i].suit;
      b[i].value=a[i].value;
    }

  for(i=0;i<n;i++)
    {
      for(j=i;j<n-1;j--)
	{
	  if(a[j].value<a[j-1].value)
	    {
	      a1=a[j];
	      a2=a[j-1];
	      a[j]=a2;
	      a[j-1]=a1;
	    }
	}
    }

  for(i=0;i<n;i++)
    {
      min=i;
      for(j=i;j<n;j++)
	{
	  if(b[j].value<b[min].value)
	    {
	      min=j;
	    }
	}
      a1=b[i];
      a2=b[min];
      b[i]=a2;
      b[min]=a1;
    }

  for(i=0;i<n-1;i++)
    {
      printf("%c%d ",a[i].suit,a[i].value);
    }
  printf("%c%d\n",a[n-1].suit,a[n-1].value);
  printf("Stable\n");

  for(i=0;i<n-1;i++)
    {
      printf("%c%d ",b[i].suit,b[i].value);
    }
  printf("%c%d\n",b[n-1].suit,b[n-1].value);

  for(i=0;i<n;i++)
    {
      if(a[i].suit!=b[i].suit)
	{
	  flag=1;
	}
    }

  if(flag==1)
    {
      printf("Not stable\n");
    }
  else {
    printf("Stable\n");
}
return 0;
}