def bubble(a, n)
	1.upto(n-1) do |i| 
	    (n-1).downto(i) do |j|
	        a[j-1], a[j] = a[j], a[j-1] if a[j-1][1] > a[j][1]
	    end
	end
end

def selection(a, n)
	0.upto(n-1) do |i|
	    minj = i
	     
	    i.upto(n-1) do |j|
	        minj = j if a[j][1] < a[minj][1]
	    end
	 
	    a[i], a[minj] = a[minj], a[i]
	end
end

def stablecheck(a, n)
	0.upto(n-2) do |i|
		return "Not stable" if a[i][1] == a[i+1][1] && A.index(a[i]) > A.index(a[i+1])
	end
	
	return "Stable"
end

N = gets.to_i
A = gets.chomp.split

a_temp = [*A]
bubble(a_temp, N)
puts a_temp.join(" ")
puts stablecheck(a_temp, N)

a_temp = [*A]
selection(a_temp, N)
puts a_temp.join(" ")
puts stablecheck(a_temp, N)
