n = gets.chomp.to_i
cards = gets.chomp.split(' ').map do |str|
  suit, value = str.split('')
  card = { suit: suit, value: value.to_i }
end

def print_cards(cards)
  cards_str = cards.map do |card|
    card[:suit] + card[:value].to_s
  end
  puts cards_str.join(' ')
end

def bubble_sort(cards)
  (0..(cards.length - 1)).each do |i|
    ((cards.length - 1)).downto(i + 1) do |j|
      if cards[j - 1][:value] > cards[j][:value]
        cards[j - 1], cards[j] = cards[j], cards[j - 1]
      end
    end
  end

  cards
end


def selection_sort(cards)
  (0..(cards.length - 1)).each do |i|
    minj = i
    (i..(cards.length - 1)).each do |j|
      if cards[j][:value] < cards[minj][:value]
        minj = j
      end
    end
    cards[i] , cards[minj] = cards[minj], cards[i]
  end

  cards
end



bubble_sort = bubble_sort(cards.dup)
print_cards(bubble_sort)
puts 'Stable'

selection_sort = selection_sort(cards.dup)
print_cards(selection_sort)
puts bubble_sort == selection_sort ? 'Stable' : 'Not stable'

