require 'pp'

size = STDIN.gets.to_i
c = STDIN.gets.split

b = c.dup
size.times do |i|
    (size-1).downto(i) do |j|
        if b[j][1] < b[j-1][1]
            b[j], b[j-1] = b[j-1], b[j]
        end
    end
end

puts b.join(' ')

def stable?(a1, a2)
    h1 = Hash.new{|h, k| h[k] = []}
    h2 = Hash.new{|h, k| h[k] = []}
    a1.each do |c|
        h1[c[1]] << c
    end
    a2.each do |c|
        h2[c[1]] << c
    end
    pp h1
    pp h2
    h1.keys.each do |k|
        if h1[k] != h2[k]
            return false
        end
    end
    return true
end

if stable?(c, b)
    puts "Stable"
else
    puts "Not stable"
end

s = c.dup
s.size.times do |i|
    min = i
    i.upto(s.size-1) do |j|
        if s[j][1] < s[min][1]
            min = j
        end
    end
    if min != i
        s[i], s[min] = s[min], s[i]
    end
end

puts s.join(' ')

if stable?(c, s)
    puts "Stable"
else
    puts "Not stable"
end