#include <bits/stdc++.h>                                                                                                                                                                                                                            
                                                                                                                                                                                                                                                    
using namespace std;                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                    
struct card {                                                                                                                                                                                                                                       
    char s;                                                                                                                                                                                                                                         
    int n;                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                    
    card() :s(' '), n(0) {}                                                                                                                                                                                                                         
                                                                                                                                                                                                                                                    
    explicit card(char s_, int n_) : s(s_), n(n_) {                                                                                                                                                                                                 
    }                                                                                                                                                                                                                                               
                                                                                                                                                                                                                                                    
    card(const card &o) : s(o.s), n(o.n) {}                                                                                                                                                                                                         
                                                                                                                                                                                                                                                    
    virtual ~card() {}                                                                                                                                                                                                                              
};                                                                                                                                                                                                                                                  
                                                                                                                                                                                                                                                    
bool operator<(const card &l, const card &r) {                                                                                                                                                                                                      
    return l.n < r.n;                                                                                                                                                                                                                               
}                                                                                                                                                                                                                                                   
bool operator>(const card &l, const card &r) {                                                                                                                                                                                                      
    return r < l;                                                                                                                                                                                                                                   
}                                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                    
bool operator==(const card &l, const card &r) {                                                                                                                                                                                                     
    return (l.n == r.n) && (l.s == r.s);                                                                                                                                                                                                            
}                                                                                                                                                                                                                                                   
bool operator!=(const card &l, const card &r) {                                                                                                                                                                                                     
    return !(l == r);                                                                                                                                                                                                                               
}                                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                    
ostream &operator<<(ostream &out, const card &c) {                                                                                                                                                                                                  
    return out << c.s << c.n;                                                                                                                                                                                                                       
}                                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                    
std::vector<card> isort(std::vector<card> A) {                                                                                                                                                                                                      
    int N = A.size();                                                                                                                                                                                                                               
    for (int i = 0; i < N; i++) {                                                                                                                                                                                                                   
        auto m = A[i];
        int mj = i;
        for (int j = i+1; j < N; j++) {
            if (m > A[j]) {
                m = min(m, A[j]);
                mj = j;
            }
        }
        if (i != mj) {
            swap(A[i], A[mj]);
        }
    }
    cout << A[0];
    for (int i = 1; i < N; i++) {
        cout << ' ' << A[i];
    }
    cout << endl;
    return A;
}

std::vector<card> bsort(std::vector<card> A) {
    int N = A.size();
    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = N-1; i > 0; i--) {
            if (A[i] < A[i-1]) {
                swap(A[i], A[i-1]);
                flag = true;
            }
        }
    }
    cout << A[0];
    for (int i = 1; i < N; i++) {
        cout << ' ' << A[i];
    }
    cout << endl;
    return A;
}

int main() {
    int N;
    cin >> N;
    vector<card> A(N);
    std::string s;

    for (int i = 0; i < N; i++) {
        cin >> s;
        A[i] = card(s[0], int(s[1]-'0'));
    }

    auto bA = bsort(A);
    cout << "Stable" << endl;
    auto iA = isort(A);
    bool eq = true;
    for (int i = 0; i < N; i++) {
        if (bA[i] != iA[i]) {
            eq = false;
            break;
        }
    }
    cout << (eq ? "Stable" : "Not stable") << endl;
}


Measured memory_bytes: 3164