#include<bits/stdc++.h>
using namespace std;

void BubbleSort(vector<pair<char,int>>& a)
{
    int N=a.size();
    for(int i=0;i<=N-2;i++){
        for(int j=N-1;j-1>=i;j--){
            if(a[j-1].second>a[j].second) swap(a[j-1],a[j]);
        }
    }
}

void SelectionSort(vector<pair<char,int>>& a)
{
    int N=a.size();
    for(int i=0;i<=N-2;i++){
        int mn=a[i].second,idx=i;
        for(int j=i+1;j<N;j++) if(a[j].second<mn){
            mn=a[j].second; idx=j;
        }
        swap(a[i],a[idx]);
    }
}

int main()
{
    int N; cin>>N;
    vector<pair<char,int>> a(N);
    for(int i=0;i<N;i++) cin>>a[i].first>>a[i].second;
    
    auto b=a;
    BubbleSort(a);
    SelectionSort(b);

    for(int i=0;i<N;i++) cout<<a[i].first<<a[i].second<<(i==N-1? '\n':' ');
    cout<<(a==a? "Stable":"Not stable")<<endl;
    for(int i=0;i<N;i++) cout<<b[i].first<<b[i].second<<(i==N-1? '\n':' ');
    cout<<(a==b? "Stable":"Not stable")<<endl;
    return 0;
}
