#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
bool ordered(int length, int* ordered_list)
{
    int sum = 0;
    for (int i = 0; i < length; i++) {
        if (ordered_list[i]) {
            sum++;
        }
    }
    for (int i = 0; i < sum; i++) {
        if (!ordered_list[i]) {
            return false;
        }
    }
    return true;
}

void check_stable(int num, std::string* list, std::string* list2)
{
    int* check_table = (int*)calloc(10, sizeof(int));
    for (int i = 0; i < num; i++) {
        int a = list[i][1] - 48;
        check_table[a] += 1;
    }

    bool no_same_num = true;
    std::vector<int> check_list;

    for (int i = 0; i < 10; i++) {
        if (check_table[i] > 1) {
            no_same_num = false;
            check_list.push_back(i);
        }
    }

    if (no_same_num) {
        std::cout << "Stable" << std::endl;
        return;
    }
    for (int i = 0; i < check_list.size(); i++) {
        std::vector<std::string> order_vector;
        for (int j = 0; j < num; j++) {
            if (list[j][1] - 48 == check_list[i]) {
                order_vector.push_back(list[j]);
            }
        }
        int order_check_flags[order_vector.size()] = {};
        for (int k = 0; k < num; k++) {
            for (int j = 0; j < order_vector.size(); j++) {
                if (order_vector[j] == list2[k]) {
                    order_check_flags[j] = 1;
                }
                if (!ordered(order_vector.size(), order_check_flags)) {

                    std::cout << "Not stable" << std::endl;
                    return;
                }
            }
        }
    }
    std::cout << "Stable" << std::endl;
    return;
}

int main()
{
    int number;
    std::cin >> number;

    std::string list[number];
    for (int i = 0; i < number; i++) {
        std::cin >> list[i];
    }
    std::string b_list[number];
    std::string s_list[number];
    for (int i = 0; i < number; i++) {
        b_list[i] = list[i];
        s_list[i] = list[i];
    }

    while (1) {
        bool bubbled = false;
        for (int i = 0; i < number - 1; i++) {
            if (b_list[i][1] > b_list[i + 1][1]) {
                std::string tmp = b_list[i];
                b_list[i] = b_list[i + 1];
                b_list[i + 1] = tmp;
                bubbled = true;
            }
        }
        if (!bubbled) {
            break;
        }
    }

    for (int i = 0; i < number; i++) {
        std::cout << b_list[i];
        if (i != number - 1) {
            std::cout << " ";
        } else {
            std::cout << std::endl;
        }
    }
    check_stable(number, list, b_list);
    for (int i = 0; i < number; i++) {
        int min = i;
        for (int j = i; j < number; j++) {
            if (s_list[j][1] < s_list[min][1]) {
                min = j;
            }
        }
        if (min != i) {
            std::string tmp = s_list[i];
            s_list[i] = s_list[min];
            s_list[min] = tmp;
        }
    }

    for (int i = 0; i < number; i++) {
        std::cout << s_list[i];
        if (i != number - 1) {
            std::cout << " ";
        } else {
            std::cout << std::endl;
        }
    }
    check_stable(number, list, s_list);
}



Measured memory_bytes: 3208