#include <iostream>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)

using namespace std;

// macro
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define DESCEND greater<int>()  // sort 降順 大きい順
#define UNIQUE(vec) (vec).erase(unique(ALL((vec))), (vec).end());  // 必ずsortを行なってから
#define MIN(vec) min_element(ALL((vec)))  // 値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする
#define zero_pad(num) setfill('0') << std::right << setw(num)  // 直後の要素をパディング
#define space_pad(num) setfill(' ') << std::right << setw(num)  // 直後の要素をパディング

// func declaration
template <class T> void printVec(vector<T>&);
template <class T> void print2DVec(vector< vector<T> >&);
template <class T> void calcVec(vector<T>&, int, char);
bool checkMultiple(vector<int>&, int);
int ctoi(const char);  // char to int

// const
const int INF = 10000000;

/*MEMO
・辞書順
abc < abcd, atcoder < atlas
・イテレータ
std::vector<int>::iterator とタイプするのは面倒なので、
 通常は型推論の auto を使用する。
 auto iter = max_element(ALL(vec));
・2次元配列
vector<vector<int>> vec = {{1, 2, 3}, {4, 5, 6}}
・20×10の配列
vector<vector<int>> vec(20, vector<int>(10, 0));
・(n, m)の多次元配列
vector< vector<int> > vec(n, vector<int>(m, 0))  // 0で初期化
*/

struct Card {
    char suit, value;  // 数字はvalueのままで比較できる
};

void BubbleSort(vector<string> &vec) {
    /*
     * 右端から隣の要素を比較して、
     * 左が大きかったら入れ替え
     * １周するとソート済みの数字が左端に1つ追加される
     */
    // prepare int_vec
    int N = vec.size();
    vector<int> int_vec(vec.size());
    REP(i, vec.size()) int_vec.at(i) = ctoi(vec.at(i).at(1));

    // BubbleSort
    REP(i, vec.size()) {
        for (int j = vec.size() - 1; i < j; --j) {
            if (int_vec.at(j-1) > int_vec.at(j)) {
                swap(int_vec.at(j-1), int_vec.at(j));
                swap(vec.at(j-1), vec.at(j));
            }
        }
    }
}

void SelectionSort(vector<string> &vec) {
    int N = vec.size();

    // prepare int_vec
    vector<int> int_vec(N);
    REP(i, N) int_vec.at(i) = ctoi(vec.at(i).at(1));

    // SelectionSort
    REP(i, N) {
        int min_idx = i;
        for (int j = i + 1; j < N; j++) {
            if (int_vec.at(min_idx) > int_vec.at(j)) {
                // 等しいときは動かさない
                min_idx = j;
            }
        }
        // ここまでで最小値のインデックスを得られる
        // ループの最後に左端と最小値を入れ替える
        swap(int_vec.at(i), int_vec.at(min_idx));
        swap(vec.at(i), vec.at(min_idx));
    }

}

bool isStable(vector<string> vec_bub, vector<string> vec2) {
    int N = vec_bub.size();
    // 構造体の配列
    Card cards_bub[N], cards2[N];
    REP(i, N) {
        // vec_bub
        cards_bub[i].suit = vec_bub.at(i).at(0);
        cards_bub[i].value = vec_bub.at(i).at(1);
        // vec2
        cards2[i].suit = vec2.at(i).at(0);
        cards2[i].value = vec2.at(i).at(1);
    }

    // 判定
    // バブルソートは常に安定なソートであるため
    // それを基準にする
    for (int i = 0; i < N; ++i) {
        if (cards_bub[i].suit != cards2[i].suit) return false;
    }
    return true;
}


int main() {
    // input
    int N;
    cin >> N;
    vector<string> vec_start(N), vec_bub, vec_sel;
    REP(i, N) cin >> vec_start.at(i);
    COPY(vec_start, vec_bub);
    COPY(vec_bub, vec_sel);

    // calculation
    BubbleSort(vec_bub);
    SelectionSort(vec_sel);

    // output
    printVec(vec_bub);
    cout << "Stable" << endl;
    printVec(vec_sel);
    if (isStable(vec_bub, vec_sel)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
    return 0;
}


// function
template <class T> void printVec(vector<T>& vec) {
    // 1要素ずつ、空白・改行なしで出力
    REP(i, vec.size()) {
        if (i) cout << " ";
        cout << vec.at(i);
    }
    cout << endl;
}

template <class T> void print2DVec(vector< vector<T> >& vec) {
    REP(i, vec.size()) {
        REP(j, vec.front().size()) {
            cout << vec.at(i).at(j);
        }
        cout << endl;
    }
}

template <class T> void calcVec(vector<T> &vec, int num, char ch) {
    // vec全体への演算
    switch (ch) {
        case '+':
            REP(i, vec.size()) vec.at(i) += num; break;
        case '-':
            REP(i, vec.size()) vec.at(i) -= num; break;
        case '*':
            REP(i, vec.size()) vec.at(i) *= num; break;
        case '/':
            REP(i, vec.size()) vec.at(i) /= num; break;
        case '%':
            REP(i, vec.size()) vec.at(i) %= num; break;
        default:
            cout << "Incorrect Operator" << endl;
    }
}

bool checkMultiple(vector<int> &vec, int num) {
    // vecの中身が、全てnumの倍数かどうかのチェック
    int count = 0;
    REP(i, vec.size()) {
        if (vec.at(i)%num != 0) count++;
    }
    return (count == 0);
}

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



Measured memory_bytes: 3216