def bubble_sort(a, n)
????c = a.dup
????(0...n).each do |i|
????????(n-1).downto(i) do |j|
????????????c[j-1], c[j] = c[j], c[j-1] if c[j-1][1] > c[j][1]
????????end
????end
????return c
end
??
def selection_sort(c, n)
????(0...n).each do |i|
????????min = i
????????(i...n).each do |j|
????????????min = j if c[j][1] < c[min][1]
????????end
????????c[i], c[min] = c[min], c[i]
????end
????return c
end
??
n = gets.to_i
a = gets.split.map { |v| [v[0], v[1].to_i] }
??
b = bubble_sort(a, n)
s = selection_sort(a, n)
??
puts b.map(&:join).join(' ')
puts "Stable"
puts s.map(&:join).join(' ')
puts b == s ? "Stable" : "Not stable"