#include<stdio.h>
typedef struct{
    int k;
    char mozi;
}card;
    
int main(){
    int i, j, m, min;
    card num[36], suit[36], temp;
     
    scanf("%d", &m);
    for(i = 0; i < m; i++){
        scanf(" %c%d", &num[i].mozi, &num[i].k);
        suit[i].mozi = num[i].mozi;
        suit[i].k = num[i].k;
    }
    
    for(i = 0; i < m; i++){
        for(j = m-1; j > i; j--){
            if(num[j].k < num[j-1].k){
                temp = num[j];
                num[j] = num[j-1];
                num[j-1] = temp;
            }
        }
    }
   
    for(i = 0; i < m-1; i++){
        printf("%c%d ",num[i].mozi, num[i].k);
    }
    printf("%c%d\nStable\n",num[i].mozi, num[i].k);
   
    for(i = 0; i < m-1; i++){
        min = i;
        for(j = i; j <= m-1; j++){
            if(suit[j].k < suit[min].k) min = j;
        }
        temp = suit[i];
        suit[i]=suit[min];
        suit[min]=temp;
    }
   
    for(i = 0; i < m-1; i++){
        printf("%c%d ",suit[i].mozi,suit[i].k);
    }
    printf("%c%d\n",suit[i].mozi,suit[i].k);
    
    for(i = 0; i < m; i++){
        if(suit[i].mozi != num[i].mozi) {
            printf("Not stable\n");
            break;
        }
    }
    if(i == m)printf("Stable\n");
    
    return 0;
}