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

def select_sort(ca)
  c = ca.dup
  c.size.times do |i|
    m = i
    i.upto(c.size - 1) do |j|
      if c[j][1] < c[m][1]
        m = j
      end
    end
    c[i], c[m] = c[m], c[i]
  end
  c
end
gets
input = gets.split.map! do |e|
  e =~ /(?<m>\w)(?<n>\d+)/
  [$1, $2.to_i]
end
a = bubble_sort(input).map(&:join).join(' ')
b = select_sort(input).map(&:join).join(' ')
puts a
puts 'Stable'
puts b
puts a == b ? 'Stable' : 'Not stable'