#include <stdio.h>

struct card{
  int num;
  char symbol;

};

int main(){

  int i,j,n,minj;
  struct card C[36],C2[36],tmp,tmp2;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%c%d",&C[i].symbol,&C[i].num);
    //  scanf("%d",&C[i].num);
    C2[i]=C[i];
  }



  for(i=0;i<n-1;i++){
    for(j=n-1;j>0;j--){

    
      if(C[j].num<C[j-1].num){
	tmp=C[j];
	C[j]=C[j-1];
	  C[j-1]=tmp;
      }

    }
  }


  for(i=0;i<n-1;i++){
    printf("%c",C[i].symbol);
    printf("%d ",C[i].num);
  }

  printf("%c",C[n-1].symbol);
  printf("%d",C[n-1].num);
  printf("\n");
  printf("Stable\n");



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

 

    if(C2[j].num<C2[minj].num)
    minj=j;

  }

  if(i!=minj){
  tmp2=C2[i];
  C2[i]=C2[minj];
  C2[minj]=tmp2;
  }
 }
 



for(i=0;i<n-1;i++){
    printf("%c",C2[i].symbol);
    printf("%d ",C2[i].num);
  }


 printf("%c",C2[n-1].symbol);
 printf("%d",C2[n-1].num);
 printf("\n");


 return 0;
}