#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string card[40],cpcard[40];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>card[i];
        cpcard[i]=card[i];
    }
    for(int i=0;i<n;i++){
        for(int j=n-1;j>i;j--){
            int a=card[j][1]-'0',b=card[j-1][1]-'0';
            if(a<b) swap(card[j],card[j-1]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<2;j++){
            cout<<card[i][j];
        }
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;
    cout<<"Stable"<<endl;
    for(int i=0;i<n;i++){
        int minj=i;
        for(int j=i;j<n;j++){
            int a=cpcard[j][1]-'0',b=cpcard[minj][1]-'0';
            if(a<b) minj=j;
        }
        swap(cpcard[i],cpcard[minj]);
    }
    for(int i=0;i<n;i++){
        cout<<cpcard[i];
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;
    bool flag=true;
    for(int i=0;i<n;i++){
        if(card[i]!=cpcard[i]) flag=false;
    }
    if(flag) cout<<"Stable"<<endl;
    else cout<<"Not stable"<<endl;
    return 0;
}

