#include <stdio.h>
#include <stdlib.h>
#define N 36

typedef struct card{
  char M; //??????????????????                                                        
  int Num;  //?????????????????°???                                                    
}Card;

void swap(Card*,Card*);
void bubbleSort(Card*,int);
void selectionSort(Card*,int);
void Printfunc(Card*,Card*,int);

int main()
{
  Card R1[N];
  Card R2[N];
  int i,j,n;
  scanf("%d",&n);
  for(i=0; i<n; i++)
    {
      scanf(" %c%d",&R1[i].M,&R1[i].Num);
      R2[i]=R1[i];
    }
  bubbleSort(R1,n);
  for(i=0; i<n; i++)
    {
      printf("%c%d",R1[i].M,R1[i].Num);
      if(i!=n-1)printf(" ");
    }
  printf("\n");
  printf("Stable\n");
  selectionSort(R2,n);
  for(i=0;i<n;i++)
    {
      printf("%c%d",R2[i].M,R2[i].Num);
      if(i!=n-1) printf(" ");
    }
printf("\n");
  Printfunc(R1, R2, n);
  return 0;
}

void bubbleSort(Card *a,int n)
{
  int i,j;
  for(i=0;i<n-1;i++)
    {
      for(j=n-1;j>i;j--)
        {
          if(a[j].Num<a[j-1].Num) swap(&a[j],&a[j-1]);
        }
    }
}

void selectionSort(Card *a,int n)
{
  int i,j,min=0,flag=0;
  for(i=0;i<n-1;i++)
    {
      min=i;
      for(j=i;j<n;j++)
        {
          if(a[j].Num<a[min].Num)
            {
              min=j;
              flag++;
            }
        }
      if(flag)    swap(&a[i],&a[min]);
    }
}

void Printfunc(Card *a1, Card *a2, int n)
{
  int i,count=0;
  for(i=0;i<n;i++)
    {
      if(a1[i].M==a2[i].M)   count++;
    }
  if(count==n) printf("Stable\n");
  else printf("Not Stable\n");
}

void swap(Card *x,Card *y)
{
  Card temp;
  temp=*x;
  *x=*y;
  *y=temp;
}