import std.stdio;
import std.conv;
import std.algorithm;
import std.range;
import std.string;
import std.typecons;
import std.math;
import std.random;
import std.range;
import std.functional;
sizediff_t minIndex(alias pred = "a < b", Range)(Range range)
if (isForwardRange!Range && !isInfinite!Range &&
    is(typeof(binaryFun!pred(range.front, range.front))))
{
    if (range.empty) return -1;

    sizediff_t minPos = 0;

    static if (isRandomAccessRange!Range && hasLength!Range)
    {
        foreach (i; 1 .. range.length)
        {
            if (binaryFun!pred(range[i], range[minPos]))
            {
                minPos = i;
            }
        }
    }
    else
    {
        sizediff_t curPos = 0;
        Unqual!(typeof(range.front)) min = range.front;
        for (range.popFront(); !range.empty; range.popFront())
        {
            ++curPos;
            if (binaryFun!pred(range.front, min))
            {
                min = range.front;
                minPos = curPos;
            }
        }
    }
    return minPos;
}


void selsort(alias pred = "a < b", T)(T a, out int sw)
{
    sw = 0;
    for (size_t i = 0; i < a.length; i++)
    {
        auto min = a[i..$].minIndex!pred + i;
        swap(a[i], a[min]);
        sw++;
    }
}
void bblsort(alias pred = "a < b", T)(T a, out int sw)
{
    sw = 0;
    for (size_t i = 0; i < a.length; i++)
    {
        for (size_t j = a.length - 1; j >= i + 1; j--)
        {
            if (binaryFun!pred(a[j], a[j - 1]))
            {
                swap(a[j], a[j - 1]);
            }
        }
    }
}
void main()
{
    readln;
    auto a = readln().strip.split(" ").array;
    int sw;
    auto b = a.dup;
    auto c = a.dup;
    b.bblsort!((x,y) => x[1..$].to!int < y[1..$].to!int)(sw);
    writeln(b.join(" "));
    writeln("Stable");
    c.selsort!((x,y) => x[1..$].to!int < y[1..$].to!int)(sw);
    writeln(c.join(" "));
    if (b.join(" ") != c.join(" "))
    {
        writeln("Not stable");
    }
    else
    {
        writeln("Stable");
    }
}
