def bubble_sort(c,n)
	for i in 0..n-1
		(i+1..n-1).reverse_each do |j|
			if c[j].to_s[1].to_i < c[j-1].to_s[1].to_i
				c[j],c[j-1] = c[j-1],c[j]
			end
		end
	end
	puts c.join(" ")
	puts "Stable"
end

def selection_sort(c,n)
	array = c.clone
	
	for i in 0..n-1
		minj = i
		for j in i..n-1
			if c[j].to_s[1].to_i < c[minj].to_s[1].to_i
				minj = j
			end
		end
		c[i],c[minj] = c[minj],c[i]
	end
	puts c.join(" ")

	flg = 1
	for i in 0..n-2
		if c[i].to_s[1].to_i == c[i+1].to_s[1].to_i
			for j in 0..n-1
				if array[j]==c[i]
					break
				elsif array[j]==c[i+1]
					flg = 0
					break
				end
			end
		end
	end
	
	if flg == 1
		puts "Stable"
	else
		puts "Not stable"
	end
end

n = gets.chomp.to_i
c = gets.chomp.split(" ")

bubble_sort(c.clone,n)
selection_sort(c.clone,n)