gets
cards = gets.split

def bubble_sort(cards)
	(cards.size - 1).times do |i|
		(cards.size - 1).downto(i + 1) do |j|
			if cards[j][1] < cards[j - 1][1]
				cards[j - 1], cards[j] = cards[j], cards[j - 1]
			end
		end
	end

	return cards
end
bubble_sorted = bubble_sort(cards.dup)
puts bubble_sorted.join(' ')
puts 'Stable'

def selection(cards)
	cards.size.times do |i|
		mini = i
		(i + 1).upto(cards.size - 1) do |j|
			mini = j if cards[j][1] < cards[mini][1]
		end

		if i != mini
			cards[i], cards[mini] = cards[mini], cards[i]
		end
	end

	return cards
end
selection_sorted = selection(cards)
puts selection_sorted.join(' ')
puts bubble_sorted == selection_sorted ? 'Stable' : 'Not stable'

