#include <stdio.h>
#include <stdlib.h>

typedef struct{
  char alp;
  int val;
}data;

void BubbleSort(data *, int);
void SelectionSort(data *, int);
void swap(data *, data *);

int main()
{
  int N, i;
  data *a, *b;
  
  a = (data *)malloc(sizeof(data)*N);
  b = (data *)malloc(sizeof(data)*N);
  
  // input
  scanf("%d", &N);
  for(i=0; i<N; i++)
    {
      getchar();
      a[i].alp = getchar();
      scanf("%d", &a[i].val);
      b[i] = a[i];
    }

  BubbleSort(a, N);
  for(i=0; i<N; i++)
    {
      printf("%c%d", a[i].alp, a[i].val);
      if(i<N-1)
	{
	  printf(" ");
	}
    }
  printf("\n");
  printf("Stable\n");

  SelectionSort(b, N);
  for(i=0; i<N; i++)
    {
      printf("%c%d", a[i].alp, a[i].val);
      if(i<N-1)
	{
	  printf(" ");
	}
    }
  printf("\n");
  if(i == N)
    {
      printf("Stable\n");
    }
  else
    {
      printf("Not stable\n");
    }
  
  return 0;
}

void BubbleSort(data *C, int N)
{
  int i, j;
  
  for(i=0; i<N-1; i++)
    {
      for(j=N-1; j>i; j--)
	{
	  if(C[j].val < C[j-1].val)
	    {
	      swap(&C[j], &C[j-1]);
	    }
	}
    }
}

void SelectionSort(data *C, int N)
{
  int i, j;
  int minj;

  for(i=0; i<N-1; i++)
    {
      minj = i;

      for(j=i+1; j<N; j++)
	{
	  if(C[j].val < C[minj].val)
	    {
	      minj = j;
	    }
	  if(minj != i)
	    {
	      swap(&C[i], &C[minj]);
	    }
	}
    }
}

void swap(data *a, data *b)
{
  data tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}