#include <stdio.h>
#include <string.h>
#define N 36
int isStable(char in[N][2],char out[N][2],int n);
int main(){
  int i,n,j,min,a1,b1,judge,flag;
  char a[N][2],b[N][2],c[N][2],change[3];
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",a[i]);
    strncpy(b[i],a[i],2);
    strncpy(c[i],a[i],2);
  }

  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(b[j][1] <b[j-1][1]){	
	strncpy(change,b[j],2);
	strncpy(b[j],b[j-1],2);
	strncpy(b[j-1],change,2);
      }
    }
  }
  for(i=0;i<n;i++){
    if(i<n-1) printf("%c%c ",b[i][0],b[i][1]);
    else printf("%c%c\n",b[i][0],b[i][1]);
  }
for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
      for(a1=0;a1<n;a1++){
	for(b1=a1+1;b1<n;b1++){
	  if(a[i][1]==a[j][1] && a[i][0]==b[b1][0] && a[j][0] == b[a1][0]){
	    judge=0;
	    flag=1;
	  }
	}
      }
    }
    if(flag==0) judge=1;
  }

  
  if(judge==0) printf("Not stable\n");
  else printf("Stable\n");

  
     for(i=0;i<n;i++){
      min=i; 
      for(j=i;j<n;j++){
	if(c[j][1]<c[min][1])	  min=j;
      }
      if(i==min) continue;
       strncpy(change,c[i],2);
       strncpy(c[i],c[min],2);
       strncpy(c[min],change,2);
      }
    for(i=0;i<n;i++){
      if(i<n-1) printf("%c%c ",c[i][0],c[i][1]);
      else printf("%c%c\n",c[i][0],c[i][1]);
    }
for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
      for(a1=0;a1<n;a1++){
	for(b1=a1+1;b1<n;b1++){
	  if(a[i][1]==a[j][1] && a[i][0]==c[b1][0] && a[j][0] == c[a1][0]){
	    judge=0;
	    flag=1;
	  }
	}
      }
    }
    if(flag==0) judge=1;
 }

    if(judge==0) printf("Not stable\n");
    else printf("Stable\n");
    return 0;
}