#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void BubbleSort(char **A,int n)
{
  int i,j;
  int buf[3];
  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");
}
void SelectionSort(char **A,int n)
{
  int i,j;
  int min;
  char buf[3];
  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");
}
int main()
{
  int n;
  char **card;
  char **card1;
  char **card2;
  int i,j;
  int f;
  scanf("%d",&n);
  card =(char**)malloc(sizeof(char*)*n);
  card1=(char**)malloc(sizeof(char*)*n);
  card2=(char**)malloc(sizeof(char*)*n);
  for(i=0;i<n;i++)
    {
      card[i] =(char*)malloc(sizeof(char)*3);
      card1[i]=(char*)malloc(sizeof(char)*3);
      card2[i]=(char*)malloc(sizeof(char)*3);
      scanf("%s",card[i]);
      strcpy(card1[i],card[i]);
      strcpy(card2[i],card1[i]);
    }
  BubbleSort(card1,n);
  for(i=1;i<n;i++)
    {
      if(card1[i-1][1]==card1[i][1])
        {
          for(j=0;j<n;j++)
            {
              if(card1[i-1][1]==card[j][1])
                {
                  if(card1[i-1][0]==card[j][0])
                    {
                      for(f=j+1;f<n;f++)
                        {
                          if(card1[i][1]==card[f][1])
                            {
                              if(card1[i][0]==card[f][0])
                                {
                                  j=n;
                                  break;
                                }
                              else
                                {
                                  printf("Not stable\n");
                                  j=n;
                                  i=n;
                                  break;
                                }
                            }
                        }
                    }
                  else
                    {
                      printf("Not stable\n");
                      i=n;
                      break;
                    }
                }
            }
        }
    }
  if(i==n)
    {
      printf("Stable\n");
    }
  SelectionSort(card2,n);
  for(i=1;i<n;i++)
    {
      if(card2[i-1][1]==card2[i][1])
        {
          for(j=0;j<n;j++)
            {
              if(card2[i-1][1]==card[j][1])
                {
                  if(card2[i-1][0]==card[j][0])
                    {
                      for(f=j+1;f<n;f++)
                        {
                          if(card2[i][1]==card[f][1])
                            {
                              if(card2[i][0]==card[f][0])
                                {
                                  j=n;
                                  break;
                                }
                              else
                                {
                                  printf("Not stable\n");
                                  j=n;
                                  i=n;
                                  break;
                                }
                            }
                        }
                    }
                  else
                    {
                      printf("Not stable\n");
                      i=n;
                      break;
                    }
                }
            }
        }
    }
  if(i==n)
    {
      printf("Stable\n");
    }
  return 0;
}

