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

int ctoi(char);
vector<tuple<int, int, char>> partial_pair_bubble(vector<tuple<int, int, char>>);
vector<tuple<int, int, char>> partial_pair_selection(vector<tuple<int, int, char>>);
vector<tuple<int, int, char>> pair_bubble(vector<tuple<int, int, char>>);
vector<tuple<int, int, char>> pair_selection(vector<tuple<int, int, char>>);

int main(int argc, char const *argv[])
{
    int n = 0;
    cin >> n;
    cin.ignore();

    vector<string> s(n, " ");
    for (int i = 0; i < n - 1; i++)
    {
        getline(cin, s[i], ' ');
    }
    getline(cin, s[n - 1], '\n');

    vector<tuple<int, int, char>> c;
    for (int i = 0; i < n; i++)
    {
        c.push_back(make_tuple(ctoi(s[i][1]), i, s[i][0]));
    }

    vector<tuple<int, int, char>> partial_bubbled_c = partial_pair_bubble(c);
    for (int i = 0; i < n - 1; i++) {
        cout << get<2>(partial_bubbled_c[i]) << get<0>(partial_bubbled_c[i]) << " ";
    }
    cout << get<2>(partial_bubbled_c[n - 1]) << get<0>(partial_bubbled_c[n - 1]) << endl;

    vector<tuple<int, int, char>> bubbled_c = pair_bubble(c);
    if (partial_bubbled_c == bubbled_c)
    {
        cout << "Stable" << endl;
    }
    else
    {
        cout << "Not stable" << endl;
    }

    vector<tuple<int, int, char>> partial_selected_c = partial_pair_selection(c);
    for (int i = 0; i < n - 1; i++)
    {
        cout << get<2>(partial_selected_c[i]) << get<0>(partial_selected_c[i]) << " ";
    }
    cout << get<2>(partial_selected_c[n - 1]) << get<0>(partial_selected_c[n - 1]) << endl;

    vector<tuple<int, int, char>> selected_c = pair_bubble(c);
    if (partial_selected_c == selected_c)
    {
        cout << "Stable" << endl;
    }
    else
    {
        cout << "Not stable" << endl;
    }

    return 0;
}

int ctoi(char c)
{
    int res = 0;
    if ('0' <= c && c <= '9')
    {
        return res = c - '0';
    }
    else
    {
        return -1;
    }
}

vector<tuple<int, int, char>> partial_pair_bubble(vector<tuple<int, int, char>> c)
{
    bool flag = true;
    while (flag == true)
    {
        flag = false;
        for (int i = c.size() - 1; i > 0; i--)
        {
            if (get<0>(c[i]) < get<0>(c[i - 1]))
            {
                tuple<int, int, char> temp = c[i];
                c[i] = c[i - 1];
                c[i - 1] = temp;
                flag = true;
            }
        }
    }
    return c;
}

vector<tuple<int, int, char>> pair_bubble(vector<tuple<int, int, char>> c)
{
    bool flag = true;
    while (flag == true)
    {
        flag = false;
        for (int i = c.size() - 1; i > 0; i--)
        {
            if (c[i] < c[i - 1])
            {
                tuple<int, int, char> temp = c[i];
                c[i] = c[i - 1];
                c[i - 1] = temp;
                flag = true;
            }
        }
    }
    return c;
}

vector<tuple<int, int, char>> partial_pair_selection(vector<tuple<int, int, char>> c)
{
    for (int i = 0; i < (int)c.size(); i++)
    {
        int min_i = i;
        for (int j = i + 1; j < (int)c.size(); j++)
        {
            if (get<0>(c[j]) < get<0>(c[min_i]))
            {
                min_i = j;
            }
        }
        if (c[i] > c[min_i])
        {
            tuple<int, int, char> temp = c[i];
            c[i] = c[min_i];
            c[min_i] = temp;
        }
    }
    return c;
}

vector<tuple<int, int, char>> pair_selection(vector<tuple<int, int, char>> c)
{
    for (int i = 0; i < (int)c.size(); i++)
    {
        int min_i = i;
        for (int j = i + 1; j < (int)c.size(); j++)
        {
            if (c[j] < c[min_i])
            {
                min_i = j;
            }
        }
        if (c[i] > c[min_i])
        {
            tuple<int, int, char> temp = c[i];
            c[i] = c[min_i];
            c[min_i] = temp;
        }
    }
    return c;
}


Measured memory_bytes: 3164