#include <stdio.h>
#include <string.h>
void swap(char *,char *);
int main()
{
  int i,j,k,l,N,count=0;
  char a[100][100],b[100][100];

  scanf("%d",&N);
  for(i=0;i<N;i++)
    {
      for(j=0;j<2;j++)
        {
          scanf("%c",&a[i][j]);
        }
    }
  for(i=0;i<N-1;i++)
    {
      for(j=1;j>0;j--)
        {
          if(a[i][j]<a[i+1][j])
            {
              swap(&a[i][j],&a[i+1][j]);
              swap(&a[i][0],&a[i+1][0]);
              count++;
            }
        }
    }
  for(i=0;i<N;i++)
    {
      for(j=0;j<2;j++)
        {
          printf("%c",a[i][j]);
        }
      if(i!=N-1) printf(" ");
    }
  printf("\n");
  printf("Stable\n");

strcpy(a,b);
  for(i=0;i<N-1;i++)
    {
      min=i;
      for(j=1;j<0;j--)
        {
          if(b[i][j]<b[i][min]) min=j;
        }
      swap(&b[i][j],&b[i][min]);
      swap(&b[i][j],&b[i][min]);
      if(i!=min) count++;
    }
   for(i=0;i<N;i++)
    {
      for(j=0;j<2;j++)
        {
          printf("%c",b[i][j]);
        }
      if(i!=N-1) printf(" ");
    }
  printf("\n");
  if(strcmp(a,b)==0)     printf("Stable\n");
  else    printf("Not stable\n");

  return 0;
}

void swap(char *x,char *y)
{
  char z;

  z=*x;
  *x=*y;
  *y=z;
}