#include <stdio.h>

typedef struct trump{
        char c;
        int m;
} card;
int n, i,j,mini,count=0;;

int main(){
        card C1[101], C2[101],key[101];
        char ch;

        scanf("%d%c", &n, &ch);
        for ( i = 1; i <= n; i++ ) {
                scanf("%c%d%c", &C1[i].c, &C1[i].m, &ch);
        }

        for ( i = 1; i <= n; i++ ) {
                C2[i]=C1[i];
        }
        for(i=1; i<=n; i++) {
                for(j=n; j>=i+1; j--) {
                        if(C1[j].c<C1[j-1].m) {
                                key[j]=C1[j];
                                C1[j]=C1[j-1];
                                C1[j-1]=key[j];
                        }
                }
        }
        for(i=1; i<=n; i++) {
                if(i==n) {
                        printf("%c%d\n",C1[i].c,C1[i].m);
                        break;
                }
                printf("%c%d ",C1[i].c,C1[i].m);
        }
        printf("Stable\n");


        for(i=1; i<=n; i++) {
                mini=i;
                for(j=i; j<=n; j++) {
                        if(C2[j].m<C2[mini].m) {
                                mini=j;
                        }
                }
                if(C2[mini].m<C2[i].m) {
                        key[i]=C2[i];
                        C2[i]=C2[mini];
                        C2[mini]=key[i];
                }
        }

        for(i=1; i<=n; i++) {
                if(i==n) {
                        printf("%c%d\n",C2[i].c,C2[i].m);
                        break;
                }
                printf("%c%d ",C2[i].c,C2[i].m);
        }
        for(i=1; i<=n; i++) {
                if(C1[i].m==C2[i].m && C1[i].c==C2[i].c) {
                        count++;
                }
                else break;
        }
        if(count==n) printf("Stable\n");
        else printf("Not stable\n");
        return 0;
}