#include <stdio.h>
#include <vector>
#include <array>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>


using std::string;
using std::vector;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// util
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// user func
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef struct _Card{
    char suit;
    int number;
} Card;


void printList(const vector<Card>& list) {
    // print
    for(int i = 0; i < list.size(); i++){
        printf("%c%d", list[i].suit, list[i].number);
        if(i != list.size() -1){
            printf(" ");
        }
    }
    printf("\n");
}


vector<Card> bubbleSort(vector<Card> list){
    // bubble sort
    for (int i = 0; i < list.size(); i++) {
        for (int j = list.size() - 1; i < j; j--) {
            if (list[j].number < list[j-1].number) {
                std::swap(list[j], list[j-1]);
            }
        }
        // printList(list);
    }
    return list;
}

static bool unstable = false;
vector<Card> insertSort(vector<Card> list){
    // insert sort
    for(int i = 0; i < list.size(); i++){
        int minIndex = i;
        for(int j = i + 1; j < list.size(); j++){
            if(list[j].number < list[minIndex].number){
               minIndex = j;
            }
        }
        if(i != minIndex) {
            std::swap(list[i], list[minIndex]);
            // printf("minIndex: %d\n", minIndex);
            // printf("i       : %d\n", i);
            for(int k = minIndex - 1; i <= k; k--){
                // printf("k: %d -> %d    min: %d -> %d\n", k, list[k].number, minIndex, list[minIndex].number);
                if(list[k].number == list[minIndex].number){
                    unstable = true;
                }
            }
        }
        // printList(list);
    }
    return list;
} 



void solve() {
    string line;
    // input n
    std::getline(std::cin, line);
    std::getline(std::cin, line);
    vector<string> elements = split(line, ' ');

    vector<Card> list;
    for(auto element: elements) {
        Card card = { element[0], std::stoi(element.substr(1, 1)) };
        list.push_back(card);
    }
    
    // printf("bubble - - - - - - - - - - - - - \n");
    vector<Card> bList = bubbleSort(list);
    printList(bList);
    printf("Stable\n");

    // printf("insert - - - - - - - - - - - - - \n");
    vector<Card> iList = insertSort(list);
    printList(iList);
    printf("%s\n", unstable? "Not stable":"Stable");
    
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    
    solve();
    
    return 0;
}


Measured memory_bytes: 3344