def b_sort(ca)
  c = ca.dup
  s = 0
  c.sort_by{|i| [i[1], s += 1]}
end

def s_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[m], c[i] = c[i], c[m]
  end
  c
end

gets
a = gets.split.map do |e|
  e =~ /(\w)(\d+)/
  [$1, $2.to_i]
end
b, c = [b_sort(a), s_sort(a)].map do |d|
  d.map(&:join).join(' ')
end
puts "#{b}\nStable"
puts "#{c}\n#{b == c ? 'Stable' : 'Not stable'}"