n = gets.to_i
card_array = gets.split(' ')

def bubble_sort(card_array, n)
  cards = card_array.dup
  (0..(n - 1)).each do |sorted_i|
    ((sorted_i + 1)..(n - 1)).reverse_each do |i|
      value = cards[i]
      if value[1] < cards[i - 1][1]
        cards[i] = cards[i - 1]
        cards[i - 1] = value
      end
    end
  end
  cards
end

def selection_sort(card_array, n)
  cards = card_array.dup
  (0..(n - 1)).each do |sorted_i|
    min_i = sorted_i
    ((sorted_i)..(n - 1)).each do |i|
      if cards[i][1] < cards[min_i][1]
        min_i = i
      end
    end
    value = cards[sorted_i]
    cards[sorted_i] = cards[min_i]
    cards[min_i] = value
  end
  cards
end

def is_stable(stable_res, item)
  return true if stable_res == item
  false
end

b_sort_res = bubble_sort(card_array, n)
puts b_sort_res.join(' ')
puts 'Stable'
s_sort_res = selection_sort(card_array, n)
puts s_sort_res.join(' ')
puts is_stable(b_sort_res, s_sort_res) ? 'Stable' : 'Not stable'

