#include<stdio.h>
#include<string.h>
struct card {
    char suit;
    int value;
};
void  swap(int*x,int*y)
{
    int  work;        /* ????\???¨ */

    work = *x;       /* x????????????????????? */
    *x = *y;          /* x?????????y???????????????????????? */
    *y = work;        /* y?????????x???????????????????????? */
}
void bubbleSort(struct card A[], const int N)
{
    int flag = 1;

    for( int i = 0; flag; ++i ){
        flag = 0;

        for( int j = N-1; i < j; --j )
            if( A[j].value < A[j-1].value ){
                swap(&A[j].value, &A[j-1].value);
                flag = 1;
            }
    }
}

void selectionSort(struct card A[], const int N)
{
    for( int i = 0; i < N; ++i ){
        int min = i;
      
        //i???????????§A[i]?????????????°???????????????????????±???????
        for( int j = i; j < N; ++j )
            if( A[j].value < A[min].value )
                min = j;
       
        //i??¨min?????°????????°??????
        if( i != min ) swap(&A[i].value, &A[min].value);
    }
}

int main()
{
    //??\???
    int N;
    scanf("%d%*c", &N);
   struct card A[N], B[N]; //A:bubbleSort, B:selectionSort
    for( int i = 0; i < N; ++i ){
        scanf("%c%d%*c", &A[i].suit, &A[i].value);
        B[i] = A[i];
    }


    bubbleSort(A, N);
    selectionSort(B, N);


    //????????????????????????????????????
    for( int i = 0; i < N; ++i ){
        if( 0 < i ) printf(" ");
        printf("%c%d", A[i].suit, A[i].value);
    }
    printf("\n");
    printf("Stable\n");

    //?????????????????????????????????
    int flag = 1;
    for( int i = 0; i < N; ++i ){
        if( 0 < i ) printf(" ");
        printf("%c%d", B[i].suit, B[i].value);
        if( !(B[i].suit == A[i].suit && B[i].value == A[i].value) ) flag = 0;
    }
    printf("\n");
    if( flag ) printf("Stable\n");
    else printf("Not stable\n");

    return 0;
}