#include<stdio.h>
#include<string.h>


int main(){
    int n,i,j;
    char mozia[36],mozib[36];
    int numa[36],numb[36];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf(" %c%d",&mozia[i],&numa[i]);
        strcpy(&mozib[i],&mozia[i]);
        numb[i]=numa[i];
    }
    //Bubble
    char tempa;
    int tempb;
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(numa[i]>numa[j]){
                tempa=mozia[i];
                mozia[i]=mozia[j];
                mozia[j]=tempa;
                tempb=numa[i];
                numa[i]=numa[j];
                numa[j]=tempb;
            }
        }
    }
    for(i=0;i<n;i++){
        if(i!=0)printf(" ");
        printf("%c%d",mozia[i],numa[i]);
    }
    printf("\nStable\n");
    
    //Select
    int minj;
    for(i=0;i<n;i++){
        minj=i;
        for(j=i;j<n;j++){
            if(numb[j]<numb[minj])minj=j;
        }
        tempa=mozib[i];
        mozib[i]=mozib[minj];
        mozib[minj]=tempa;
        tempb=numb[i];
        numb[i]=numb[minj];
        numb[minj]=tempb;
    }
    for(i=0;i<n;i++){
        if(i!=0)printf(" ");
        printf("%c%d",mozib[i],numb[i]);
    }
    printf("\n");
    for(i=0;i<n;i++){
        if(mozia[i]!=mozib[i]){
            printf("Not stable\n");
            return 0;
        }
    }
    printf("Stable\n");
    
    return 0;
}


