#include <stdio.h>
#include <math.h>
int main(void){
    char c[37],d[37],tc;
    int m,f=0,n,i,j,a[36],b[36],ti;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf(" %c%d",&c[i],&a[i]);
    for(i=0;i<n;i++){
    	b[i]=a[i];
    	d[i]=c[i];
    }
    for(i=0;i<n;i++){
    	for(j=n-1;j>=i+1;j--){
    		if(a[j]<a[j-1]){
    			ti=a[j];
    			a[j]=a[j-1];
    			a[j-1]=ti;
    			tc=c[j];
    			c[j]=c[j-1];
    			c[j-1]=tc;
    		}
    	}
    }
    for(i=0;i<n;i++){
    	m=i;
    	for(j=i;j<n;j++){
    		if(b[j]<b[m]){
    			m=j;
    		}
    	}
    	ti=b[m];
    	b[m]=b[i];
    	b[i]=ti;
    	tc=d[m];
    	d[m]=d[i];
    	d[i]=tc;
    }
    for(i=0;i<n;i++){
    	if(i!=0) printf(" ");
    	printf("%c%d",c[i],a[i]);
    }
    printf("\nStable\n");
    for(i=0;i<n;i++){
    	if(i!=0) printf(" ");
    	printf("%c%d",d[i],b[i]);
    }
    for(i=0;i<n;i++){
    	if(c[i]!=d[i]) f=1;
    }
    if(f){
    	printf("\nNot Stable\n");
    }else{
    	printf("\nStable\n");
    }
    return 0;
}
