#include<stdio.h>
int main(void){
  int i,j,n,len,mini,t,hantei=0,num;
  int A[36],B[36];
  char a[36],b[36],c,TF,TT;
  scanf("%d",&len);
  for(i=0;i<len;i++){
    scanf("%c%c%d",&c,&a[i],&A[i]);
  }
  for(i=0;i<len;i++){
    B[i]=A[i];
    b[i]=a[i];
    for(j=0;j<i;j++){
      if(A[i]==A[j]){
	TF=a[j];
	hantei=1;
	num=A[j];
      }
    }
  }

 for(i=0;i<len;i++){
    for(j=len-1;j>i;j--){
      if(A[j]<A[j-1]){
	t=A[j];
	A[j]=A[j-1];
	A[j-1]=t;
	c=a[j];
	a[j]=a[j-1];
	a[j-1]=c;


      }
    }
  }
  for(i=0;i<len;i++){
    if(i!=0){
      printf(" ");
    }
    printf("%c%d",a[i],A[i]);
  }
  printf("\n");
  if(hantei==1){
    for(i=0;i<len;i++){
      if(A[i]==num){
	if(a[i]!=TF){
      printf("Not stable\n");
      break;
	}
	printf("Stable\n");
	break;
      }
    }
  }
  else printf("Stable\n");



   for(i=0;i<len;i++){
    mini=i;
    for(j=i;j<len;j++){
      if(B[j]<B[mini]){
	mini=j;
      }
    }
    if(i!=mini){
    t=B[i];
    B[i]=B[mini];
    B[mini]=t;
    c=b[i];
    b[i]=b[mini];
    b[mini]=c;
    }
  }
  for(i=0;i<len;i++){
    if(i!=0){
      printf(" ");
    }
    printf("%c%d",b[i],B[i]);
  }
  printf("\n");
  if(hantei==1){
    for(i=0;i<len;i++){
      if(B[i]==num){
	if(b[i]!=TF){
      printf("Not stable\n");
      break;
	}
	printf("Stable\n");
	break;
      }
    }
  }
  else printf("Stable\n");

  return 0;
}