#include <stdio.h>
#define N 36

struct card{
  char mark;
  int value;
};

int main(){

  int n,l;
  int i,j;
  char ch;
  int temp1,temp2;
  int min;

  struct card C[N],A[N];
  scanf("%d%c",&n,&ch);

    for(l=0;l<n;l++){
      scanf("%c%d%c",&C[l].mark,&C[l].value,&ch);
  }

    for(i=0;i<n+1;i++)A[i]=C[i];
    
    for(i=0;i<n-1;i++){

      for(j=n-1;j>i;j--){
	if(C[j].value<C[j-1].value){
	  temp1=C[j].value;
	  C[j].value=C[j-1].value;
	  C[j-1].value=temp1;
	  ch=C[j].mark;
	  C[j].mark=C[j-1].mark;
	  C[j-1].mark=ch;
	}
      }
    }

    for(i=0;i<n-1;i++){
      min=i;
      for(j=i;j<n;j++){
	if(A[j].value<A[min].value)min=j;
      }
      temp2=A[i].value;
      A[i].value=A[min].value;
      A[min].value=temp2;
      ch=A[i].mark;
      A[i].mark=A[min].mark;
      A[min].mark=ch;
    }

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

    for(i=0;i<n-1;i++){
      printf("%c%d ",A[i].mark,A[i].value);
    }
     printf("%c%d",A[i].mark,A[i].value);
    printf("\nNot stable\n");


    
    return 0;
}


