#include<stdio.h>
#define MAX 36

typedef struct {
  char op;
  int value;
}c;

int N;
int isStable(c *,c *);
int main(){
  int i,j,min,minj,x,a,b;
  char dummy;
  c C[MAX];
  scanf("%d",&N);
  for(i=0;i<N;i++){  
    scanf("%c%d%c",&C[i].op,&C[i].value,&dummy);
  }
  for(i=0;i<N-1;i++){
    for(j=N-1;N>=0;N--){
      if(C[j].value<C[j-1].value)
	min=C[j].value;
      C[j].value=C[j-1].value;
      C[j-1].value=min;
    }}
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%c%d",C[i].op,C[i].value);
  }
  printf("\n");
  if(isStable(C,C)==0)
    printf("Not stable\n");
    if(isStable(C,C)==1)
      printf("Stable\n");
    
    for(i=0;i<=N-1;i++){
      minj=i;
      for(j=i;j<=N-1;j++){
    if(C[j].value<C[minj].value)
      minj=j;
      x=C[minj].value;
      C[minj].value=C[i].value;
      C[i].value=x;
      }}

   for(i=0;i<N;i++){
      if(i>0) printf(" ");
      printf("%c%d",C[i].op,C[i].value);
    }
    printf("\n");
    if(isStable(C,C)==0)
      printf("Not stable\n");
    if(isStable(C,C)==1)
      printf("Stable\n");
    return 0;
  }
    

	   
int isStable(c *in,c *out){
  int i,j,a,b;
  for(i=0;i<N-1;i++){
    for(j=i+1;j<N-1;j--){
      for(a=0;a<N-1;a++){
	for(b=a+1;b<N-1;b++){
	  if(in[i].value==in[j].value && in[i].op==out[b].op && in[j].op==out[a].op)
	    return 0;
	}}}}
  return 1;
}	  