#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);

int n;

class m_int{
    public:
    int_fast32_t MOD = max_int;
    int_fast32_t d=0;
    m_int operator =(int x){
        this->d = (int_fast32_t)x;
        return *this;
    }
    m_int operator =(const m_int x){
        this->d = x.d;
        return *this;
    }
    m_int operator+(const m_int &another) const{
        m_int tmp;
        if(d+another.d>MOD){
            tmp.d = d+another.d-MOD;
            return tmp;
        }
        else{
            tmp.d = d+another.d;
            return tmp;
        }
    }
    m_int operator+=(const m_int another){
        (*this) = (*this) + another;
        return *this;
    }
    m_int operator-(const m_int &another) const{
        m_int tmp;
        if(d-another.d<(int_fast32_t)0){
            tmp.d = d-another.d+MOD;
            return tmp;
        }
        else{
            tmp.d = d-another.d;
            return tmp;
        }
    }
    m_int operator*(const m_int &another) const{
        m_int tmp;
        tmp.d = d*another.d%MOD;
        return tmp;
    }
    m_int operator*(int x){
        m_int tmp;
        tmp.d = d*x%MOD;
        return tmp;
    }
    /*
    m_int operator/(const m_int &another) const{
        m_int tmp;
        if(d-another.d<(int_fast32_t)0){
            tmp.d = d-another.d+MOD;
            return tmp;
        }
        else{
            tmp.d = d-another.d;
            return tmp;
        }
    }*/
    bool operator<(const m_int &another) const{
        return d < another.d;
    }
    bool operator>(const m_int &another) const{
        return d > another.d;
    }
};
ostream& operator<<(std::ostream& os, const m_int& obj){
    // ここでストリームに obj を書き込みます。
    os << obj.d;
    return os;
}
istream& operator>>(std::istream& is, m_int& obj){
    // ここでストリームから obj を読み込みます。
    is >> obj.d;
    if( false ) is.setstate(std::ios::failbit);
    return is;
}

class trump{
    public:
    string data;
    bool operator<(const trump &another) const{
        return data[1] < another.data[1];
    }
    bool operator>(const trump &another) const{
        return data[1] > another.data[1];
    }
    bool operator!=(const trump &another) const{
        return data != another.data;
    }

};
ostream& operator<<(std::ostream& os, const trump& obj){
    // ここでストリームに obj を書き込みます。
    os << obj.data;
    return os;
}
istream& operator>>(std::istream& is, trump& obj){
    // ここでストリームから obj を読み込みます。
    is >> obj.data;
    if( false ) is.setstate(std::ios::failbit);
    return is;
}

void bub_sort(vector<trump>& a,int n){
    REP(i,n-1){
        for(int j=n-1;j >= i+1;j--){
            if(a[j] < a[j-1]){
                swap(a[j],a[j-1]);
            }
        }
    }
}
void sel_sort(vector<trump>& a,int n){
    REP(i,n){
        int minj = i;
        FOR(j,i,n){
            if(a[j] < a[minj]) minj = j;
        }
        swap(a[i],a[minj]);
        //Debug(a);
    }
}



signed main(){
    cin >> n;
    vector<trump> a(n);
    vector<trump> b(n);
    vector<trump> c(n);
    input(a,n);
    copy(a.begin(),a.end(),c.begin());
    //answer
    Sort(b);
    bub_sort(c,n);
    REP(i,n){
        cout << c[i];
        if(i != n-1) cout << " ";
    }
    print("");
    bool ans = true;
    REP(i,n){
        if(c[i] != b[i]){
            ans = false;
        }
    }
    print("Stable");
    copy(c.begin(),c.end(),b.begin());
    copy(a.begin(),a.end(),c.begin());
    sel_sort(c,n);
    REP(i,n){
        cout << c[i];
        if(i != n-1) cout << " ";
    }
    print("");
    ans = true;
    REP(i,n){
        if(c[i] != b[i]){
            ans = false;
        }
    }
    ans ? print("Stable"):print("Not stable");

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}



Measured memory_bytes: 3148