n = gets.to_i
cards = gets.split

value = ->(card) {
  card[1].to_i
}

bubble_sort = ->(ar) {
  n.times do |i|
    (n - 1).downto(i + 1) do |j|
      ar[j], ar[j - 1] = ar[j - 1], ar[j] if value.(ar[j]) < value.(ar[j - 1])
    end
  end
  ar
}

selection_sort = ->(ar) {
  result = "Stable"
  n.times do |i|
    minj = i
    f = false
    (i + 1).upto(n - 1) do |j|
      f = true if ar[i] == ar[j]
      if value.(ar[j]) < value.(ar[minj])
        minj = j
        result = "Not stable" if f
      end
    end
    ar[i], ar[minj] = ar[minj], ar[i]
  end
  [ar, result]
}

puts bubble_sort.(cards.dup).join(" ")
puts "Stable"
ar, result = selection_sort.(cards.dup)
puts ar.join(" ")
puts result

