def bubbleSort(n, a)
	s = a.map{|i| i.delete("^0-9").to_i}
	flag = 1
	while flag==1 do
		flag = 0
		i = 0
		(n-1).downto(i+1) do |j|
			if s[j].to_i<s[j-1].to_i then
				v = s[j];s[j] = s[j-1];s[j-1] = v
				v = a[j];a[j] = a[j-1];a[j-1] = v
				flag = 1
			end
		end
		i += 1
	end
	return a
end

def selectionSort(n, a)
	s = a.map{|i| i.delete("^0-9").to_i}
	0.upto(n-1) do |i|
		minj = i
		i.upto(n-1) do |j|
			minj = j if s[j].to_i<s[minj].to_i
		end
		v = s[i];s[i] = s[minj];s[minj] = v
		v = a[i];a[i] = a[minj];a[minj] = v
	end
	return a
end

n = gets.to_i
a = gets.split.map(&:to_s)
a1, a2 = Array.new
a1 = a.dup
a2 = a.dup
s1 = bubbleSort(n, a1)
s2 = selectionSort(n, a2)
puts s1.join(' ')
puts "Stable"
puts s2.join(' ')
puts (s1 == s2) ? "Stable" : "Not stable"
