#include<iostream>
using namespace std;
int main() {
    int x, minj;
    cin >> x;
    string A[x], B[x], word = "Stable";
    for ( int i = 0; i < x; i++ ){
        cin >> A[i];
        B[i] = A[i];
    }
    for ( int i = 0; i < x; i++ ){
        for ( int j = x-1; j > i; j-- ){
            if ( A[j][1] < A[j-1][1] ){
                swap( A[j],A[j-1] );
            }
        }
    }
    for ( int i = 0; i < x; i++ ){
        if ( i == x-1 ){
            cout << A[i] << endl;
        } else {
            cout << A[i] << " ";
        }
    }
    cout << "Stable" << endl;
    for ( int i = 0; i < x; i++ ){
        minj = i;
        for ( int j = i; j < x; j++ ){
            if ( B[j][1] < B[minj][1] ){
                minj = j;
            }
        }
        swap( B[i], B[minj] );
    }
    for ( int i = 0; i < x; i++ ){
        if ( i == x-1 ){
            cout << B[i] << endl;
        } else {
            cout << B[i] << " ";
        }
        if (A[i] != B[i]) word ="Not stable";
    }
    cout << word << endl;
    return 0;
}

