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"