#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define _GLIBCXX_DEBUG
using namespace std;

int bubbleSort(vector<pair<char, int> > &a, int n)
{
    bool flag = true;
    int count = 0;

    rep(i, n)
    {
        for (int j = n - 1; j >= i + 1; j--)
        {
            if (a.at(j).second < a.at(j - 1).second)
            {
                swap(a.at(j), a.at(j - 1));
                count++;
            }
        }
    }
    /*
    while (flag)
    {
        flag = false;
        for (int j = n - 1; j > 0; j--)
        {
            if (a.at(j) < a.at(j - 1))
            {
                swap(a.at(j), a.at(j - 1));
                count++;
                flag = true;
            }
        }
    }
    */
    return count;
}

int selectionSort(vector<pair<char, int> > &a, int n)
{
    int count = 0;

    rep(i, n)
    {
        int minj = i;
        for (int j = i; j < n; j++)
        {
            if (a.at(j).second < a.at(minj).second)
            {
                minj = j;
            }
        }

        swap(a.at(i), a.at(minj));
        count++;
    }
    return count;
}

int main()
{
    int N;
    cin >> N;

    vector<pair<char, int> > a(N);

    // 重複数値チェック
    vector<int> count(9);
    vector<string> keys(9);
    bool stablecheck = false;
    rep(i, N)
    {
        string s;
        cin >> s;
        a.at(i) = make_pair(s.at(0), (int)(s.at(1) - '0'));
        count.at(a.at(i).second - 1)++;
        if (count.at(a.at(i).second - 1) > 1)
            stablecheck = true;
        keys.at(a.at(i).second - 1).push_back(a.at(i).first);
    }

    /* デバッグ用
    rep(i, N)
    {
        cout << a.at(i).first << a.at(i).second << endl;
    }

    rep(i, 9)
    {
        cout << i + 1 << " count: " << count.at(i);
        cout << " key: " << keys.at(i) << endl;
    }
    */
    
    vector<pair<char, int> > bubble(N);

    // バブルソート
    bubble = a;
    bubbleSort(bubble, N);
    bool stable = true;

    // ソート後の出力
    rep(i, N)
    {
        if (i)
        {
            cout << " ";
        }
        cout << bubble.at(i).first << bubble.at(i).second;
    }
    cout << endl;
    // 安定チェック
    if (stablecheck)
    {
        rep(i, 9)
        {
            if (count.at(i) > 1)
            {
                for (int j = 0; j < N; j++)
                {
                    if (bubble.at(j).second - 1 == i)
                    {
                        for (int k = 0; k < count.at(i); k++)
                        {
                            if (bubble.at(j).first != keys.at(i)[k])
                            {
                                //cout << "Swap detect:" << bubble.at(j).first << " Correct:" << keys.at(i)[k] << endl;
                                stable = false;
                                break;
                            }
                            else
                            {
                                j++;
                            }
                        }
                    }
                }
            }
        }
    }
    string ans = stable ? "Stable" : "Not stable";
    cout << ans << endl;

    // 選択ソート
    stable = true;
    vector<pair<char, int> > selection(N);
    selection = a;
    selectionSort(selection, N);

    // ソート後の出力
    rep(i, N)
    {
        if (i)
        {
            cout << " ";
        }
        cout << selection.at(i).first << selection.at(i).second;
    }
    cout << endl;
    // 安定チェック
    if (stablecheck)
    {
        rep(i, 9)
        {
            if (count.at(i) > 1)
            {
                for (int j = 0; j < N; j++)
                {
                    if (selection.at(j).second - 1 == i)
                    {
                        for (int k = 0; k < count.at(i); k++)
                        {
                            if (selection.at(j).first != keys.at(i)[k])
                            {
                                //cout << "Swap detect:" << bubble.at(j).first << " Correct:" << keys.at(i)[k] << endl;
                                j = N;
                                stable = false;
                                break;
                            }
                            else
                            {
                                j++;
                            }
                        }
                    }
                }
            }
        }
    }

    ans = stable ? "Stable" : "Not stable";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3232