/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=ja 
ALDS1_2_A:バブルソート
*/

#include <bits/stdc++.h>

using namespace std;

void disp(unsigned short int *n, unsigned short int N);
int bubble_sort(unsigned short int *n, unsigned short int N);
int selection_sort(unsigned short int *n, unsigned short int N);


class Cards{
    public:
        char mark;
        unsigned short int value;
};

int main(void){

	unsigned short int N;
	scanf("%d", &N);

	string n[N]; //ex. H2, D6 

    Cards cards[N], cards_2[N];

    //char cards[N][2];
	for(int i=0; i<N; i++) {
		cin >> n[i];
        cards[i].mark = n[i][0];
        cards[i].value = int(n[i][1])-48;//ASCII to Int. ex.53 means 5 on ASCII

        cards_2[i].mark = n[i][0];
        cards_2[i].value = int(n[i][1])-48;//ASCII to Int. ex.53 means 5 on ASCII
	}

    //printf("(cards[1].mark, cards[1].value)=(%c, %d)\n", cards[1].mark, cards[1].value);
    //bubble_sort (Stable)
    int max = N-1;
    int flag;
    if(N >= 2){
        flag = 1; //ソート終了フラグ
    }else if(N<=1) flag = 0;
    int count=0; //交換回数
    
    while(flag == 1){
        for(int i=0; i<max; i++){
            if(cards[i].value > cards[i+1].value){
                //count += 1;
                unsigned short int tmpv = cards[i].value;
                cards[i].value = cards[i+1].value;
                cards[i+1].value = tmpv;

                unsigned short int tmpm = cards[i].mark;
                cards[i].mark = cards[i+1].mark;
                cards[i+1].mark = tmpm;
            }
        }
        max = max-1;
        if(max == 0) flag = 0;
    }
    for(int i=0; i<N; i++) {
		printf("%c%d", cards[i].mark, cards[i].value);
		if( i != N-1) printf(" ");
	}
	printf("\n");
    printf("Stable\n");

    //Selection Sort(Not Stable)

    for(int i=0; i<N-1; i++){
        int minj = i;
        for(int j=i; j<N; j++){
            if(cards_2[j].value < cards_2[minj].value){
                minj = j;
                }
            }
        
        if(minj != i){
            unsigned short int tmpv = cards_2[i].value;
            cards_2[i].value = cards_2[minj].value;
            cards_2[minj].value = tmpv;

            unsigned short int tmpm = cards_2[i].mark;
            cards_2[i].mark = cards_2[minj].mark;
            cards_2[minj].mark = tmpm;
        }
    }

    for(int i=0; i<N; i++) {
		printf("%c%d", cards_2[i].mark, cards_2[i].value);
		if( i != N-1) printf(" ");
	}
	printf("\n");

    bool isStable = true;
    for(int i=0; i<N; i++){
        if(cards[i].mark != cards_2[i].mark){
            isStable = false;
            break;
        }  
    }
    if(isStable) printf("Stable\n");
    else printf("Not stable\n");
    //int count = bubble_sort(n, N);
    //int count = selection_sort(n, N);   

    //disp(n, N);
    //printf("%d\n",count);
    
	return 0;
	
  
}

void disp(unsigned short int *n, unsigned short int N){
	//printf("disp: ");
	for(int i=0; i<N; i++) {
		printf("%d", n[i]);
		if( i != N-1) printf(" ");
	}
	printf("\n");
}

int bubble_sort(unsigned short int *n, unsigned short int N){
    int max = N-1;
    int flag;
    if(N >= 2){
        flag = 1; //ソート終了フラグ
    }else if(N<=1) flag = 0;
    int count=0; //交換回数
    while(flag == 1){
        for(int i=0; i<max; i++){
            if(n[i] > n[i+1]){
                count += 1;
                unsigned short int tmp = n[i];
                n[i] = n[i+1];
                n[i+1] = tmp;
            }
        }
        max = max-1;
        if(max == 0) flag = 0;
    }

    return count;
}

int selection_sort(unsigned short int *n, unsigned short int N){
    int count = 0;
    int flag;

    for(int i=0; i<N-1; i++){
        int minj = i;
        for(int j=i; j<N; j++){
            if(n[j] < n[minj]){
                minj = j;
                }
            }
        
        if(minj != i){
            count +=1;
            unsigned int tmp = n[i];
            n[i] = n[minj];
            n[minj] = tmp;
        }
    }
    return count;
}


Measured memory_bytes: 3272