
class Ele
    attr_reader :data
    def initialize(data)
        @data = data
    end
    
    def <=>(t)
        @data[1] <=> t.data[1]
    end
end

gets
a = gets.split(" ").map{ |x| Ele.new(x) }

def bubble(d)
    a = d.clone
    a.size.times do |i|
        (a.size - i - 1).times do |j|
            if (a[j] <=> a[j + 1]) > 0 then
                a[j], a[j + 1] = a[j + 1], a[j]
            end
        end
    end
    
    a
end

def select(d)
    a = d.clone
    
    b = true
    a.size.times do |i|
        x = i
        ((i + 1)...a.size).each do |j|
            if (a[j] <=> a[x]) < 0 then
                x = j
            elsif (a[j] <=> a[x]) == 0 then
            end
        end

        (x - 1).downto(i + 1) do |k|
            if (a[k] <=> a[x]) == 0 || (a[k] <=> a[i]) == 0 then
                b = false
            end
        end

        a[i], a[x] = a[x], a[i]
    end
    
    return b, a
end

print bubble(a).map{ |x| x.data }.join(" "), "\n"
print "Stable\n"
b = false
b, a = select(a)
print a.map{ |x| x.data }.join(" "), "\n"
print b ? "Stable\n" : "Not stable\n"

