
#include<stdio.h>

typedef struct{
  int value;
  char length;
}C;

int main()
{
  int i,j,n,flag=0,x,minj,count;
  char c;
  C C[36],M[36];

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%c%d",&C[i].length,&C[i].value);
      M[i]=C[i];
    }
flag=1;
  i=0;

  while(flag){
    flag=0;
    for(j=n-1;j>=i+1;j--)
      {
	if(C[j].value<C[j-1].value)
	  {
	    x = C[j].value;
	    c = C[j].length;
	    C[j].value= C[j-1].value;
	    C[j].length= C[j-1].length;
	    C[j-1].value= x;
	    C[j-1].length= c;
	    flag=1; 
	    count++;     
	  }   
      }
    i++;  
  }
   
 
  for(i=0;i<n;i++)
    {
      printf("%c%d",C[i].length,C[i].value); 
      if(i==n-1)
	printf("\n");
      else
	printf(" ");
    }

  printf("Stable\n");
   
 
   
  for(i=0;i<=n-1;i++){
    minj=i;
    flag=0;
    for(j=i;j<=n-1;j++){
      if(M[j].value<M[minj].value){
	minj=j;
	flag=1;
      }
    }
    if(flag==1){
      x = M[i].value;
      c = M[i].length;
      M[i].value= M[minj].value;
      M[i].length= M[minj].length;
      M[minj].value= x;
      M[minj].length= c;
      count++;

    }
  }
  for(i=0;i<n;i++)
    {
      printf("%c%d",M[i].length,M[i].value);
      if(i!=n-1)
	printf(" ");
    }
  printf("\n");
  for(i=0;i<n;i++)
    {
      if(C[i].length!=M[i].length)
	flag=1;
    }
  if(flag==1)
    printf("Not stable\n");
  else{
    printf("Stable\n");
  }
  return 0;
}