MODE = "stdio"
#require 'matrix'
#include Math
line = Array.new

if(defined? MODE)
  line = STDIN.read.split("\n")
else
  tmp = '5
  S7 D3 D4 C1 H3'.split("\n")
  tmp.each{|s|
    line << s.strip
  }
end

n = line[0].to_i

arr = line[1].split(" ")
arr2 = line[1].split(" ")

i=0
(0..n-1).each do |i|
  (n-1).downto(i+1) do |j|
    if arr2[j][1]<arr2[j-1][1]
      arr2[j], arr2[j-1] = arr2[j-1], arr2[j]
    end
  end
  i+=1
end



(0..n-1).each do |i|
  minj = i
  (i..n-1).each do |j|
    if arr[j][1]<arr[minj][1]
      minj = j
    end
  end
  if i!=minj
    arr[i],arr[minj] = arr[minj],arr[i]
  end
end

puts arr2.join(" ")
puts "Stable"
puts arr.join(" ")
puts "Not stable" if arr2 != arr
puts "Stable" if arr2 == arr