#include<iostream>
#include<algorithm>

using namespace std;

int number=0;
string cards[100];
string cards1[100];
string cards2[100];

void bubble_sort(string a[]);
void selection_sort(string a[]);
void stability(string before[], string after[]);
void print(string a[]);

int main(){
    cin>>number;
    for (int i=0; i<number; i++) {
        cin>>cards[i];
        cards1[i]=cards[i];
        cards2[i]=cards[i];
    }
    bubble_sort(cards1);
    print(cards1);
    stability(cards, cards1);
    selection_sort(cards2);
    print(cards2);
    stability(cards, cards2);
}

void bubble_sort(string a[]){
    for (int i=0; i<number; i++) {
        for (int j=number-1; j>i; j--) {
            if ((int)a[j][1] < (int)a[j-1][1]) {
                swap(a[j],a[j-1]);
            }
        }
    }
}

void selection_sort(string a[]){
    for (int i=0; i<number; i++) {
        int mini = i;
        for (int j=i; j<number; j++) {
            if ( atoi(&a[j][1]) < atoi(&a[mini][1]) ) {
                mini = j;
            }
        }
        if (i!=mini) {
            swap(a[i],a[mini]);
        }
    }
}

void stability(string before[],string after[]){
    bool stable = true;
    //table : 0:S 1:H 2:C 3:D
    int tableBefore[9][4];
    int numberOfAppearanceBefore[9];
    int tableAfter[9][4];
    int numberOfAppearanceAfter[9];
    for (int i=0; i<9; i++) {
        for (int j=0; j<4; j++) {
            tableBefore[i][j]=0;
            tableAfter[i][j]=0;
        }
        numberOfAppearanceBefore[i]=0;
        numberOfAppearanceAfter[i]=0;
    }
    for (int i=0; i<number; i++) {
        int numberOfCard = atoi(&before[i][1]);
        switch (before[i][0]) {
            case 'S':
                numberOfAppearanceBefore[numberOfCard-1]++;
                tableBefore[numberOfCard-1][0] = numberOfAppearanceBefore[numberOfCard-1];
                break;
            case 'H':
                numberOfAppearanceBefore[numberOfCard-1]++;
                tableBefore[numberOfCard-1][1] = numberOfAppearanceBefore[numberOfCard-1];
                break;
            case 'C':
                numberOfAppearanceBefore[numberOfCard-1]++;
                tableBefore[numberOfCard-1][2] = numberOfAppearanceBefore[numberOfCard-1];
                break;
                
            case 'D':
                numberOfAppearanceBefore[numberOfCard-1]++;
                tableBefore[numberOfCard-1][3] = numberOfAppearanceBefore[numberOfCard-1];
                break;
                
            default:
                break;
        }
    }
    for (int i=0; i<number; i++) {
        int numberOfCard = atoi(&after[i][1]);
        switch (after[i][0]) {
            case 'S':
                numberOfAppearanceAfter[numberOfCard-1]++;
                tableAfter[numberOfCard-1][0] = numberOfAppearanceAfter[numberOfCard-1];
                break;
            case 'H':
                numberOfAppearanceAfter[numberOfCard-1]++;
                tableAfter[numberOfCard-1][1] = numberOfAppearanceAfter[numberOfCard-1];
                break;
            case 'C':
                numberOfAppearanceAfter[numberOfCard-1]++;
                tableAfter[numberOfCard-1][2] = numberOfAppearanceAfter[numberOfCard-1];
                break;
            case 'D':
                numberOfAppearanceAfter[numberOfCard-1]++;
                tableAfter[numberOfCard-1][3] = numberOfAppearanceAfter[numberOfCard-1];
                break;
                
            default:
                break;
        }
    }
    for (int i=0; i<9; i++) {
        for (int j=0; j<4; j++) {
            if (tableBefore[i][j] != tableAfter[i][j]) {
                stable = false;
                break;
            }
        }
    }
    if (stable) {
        cout<<"Stable"<<endl;
    }else{
        cout<<"Not stable"<<endl;
    }
}

void print(string a[]){
    for (int i=0; i<number-1; i++) {
        cout<<a[i]<<" ";
    }
    cout<<a[number-1]<<endl;
}

Measured memory_bytes: 1216