n = gets.to_i
cs = gets.split

cs_b = cs.dup

(0..n-1).each do |i|
  (n-1).downto(i+1) do |j|
    if cs_b[j][1].to_i < cs_b[j-1][1].to_i
      tmp = cs_b[j]
      cs_b[j] = cs_b[j-1]
      cs_b[j-1] = tmp
    end
  end
end

puts cs_b.join(" ")
puts 'Stable'

cs_s = cs.dup

(0..n-1).each do |i|
  minj = i
  (i..n-1).each do |j|
    if cs_s[j][1].to_i < cs_s[minj][1].to_i
      minj = j
    end
  end
  next if cs_s[i] == cs_s[minj]
  tmp = cs_s[i]
  cs_s[i] = cs_s[minj]
  cs_s[minj] = tmp
end
puts cs_s.join(" ")
puts cs_s == cs_b ? 'Stable' : 'Not stable'




