N = gets.to_i
C = gets.split.map{|c| [c[0], c[1].to_i]}

bubble = ->(ary) do
  swap = true
  while swap
    swap = false
    0.step(N-2) do |i|
      ary[i], ary[i+1], swap = ary[i+1], ary[i], true if ary[i][1] > ary[i+1][1]
    end
  end
  ary.map(&:join).join ' '
end

selection = ->(ary) do
  0.step(N-1) do |i|
    min = i
    i.step(N-1) do |j|
      min = j if ary[min][1] > ary[j][1]
    end
    ary[i], ary[min] = ary[min], ary[i]
  end
  ary.map(&:join).join ' '
end

b = bubble.(C.dup)
puts b
puts 'Stable'
s = selection.(C.dup)
puts s
puts (b == s ? 'Stable' : 'Not stable')
