N = gets.to_i
cards = gets.split

suit, nums = cards.map{|x|x[0]}, cards.map{|x|x[1].to_i}
cards = suit.zip(nums)

#BubbleSort
array = Marshal.load(Marshal.dump(cards))
0.upto(N-1) do |i|
	(N-1).downto(i+1) do |j|
		#puts "i = #{i}, j = #{j}, j-1 = #{j-1}"
		if array[j][1] < array[j-1][1]
			array[j], array[j-1] = array[j-1], array[j]
			#puts array.map{|arr| arr[0] + arr[1].to_s}.join(" ")
		end
	end
end

puts array.map{|arr| arr[0] + arr[1].to_s}.join(" ")
puts "Stable"

#SelectionSort
array2 = Marshal.load(Marshal.dump(cards))
0.upto(N-1) do |i|
	minj = i
	i.upto(N-1) do |j|
		if array2[j][1] < array2[minj][1]
			minj = j
		end
	end
	array2[i], array2[minj] = array2[minj], array2[i] if i != minj
end

puts array2.map{|arr| arr[0] + arr[1].to_s}.join(" ")

if array == array2
	puts "Stable"
else
	puts "Not stable"
end