def calc_a_order arr
  a_order = [[], [], [], [], [], [], [], [], []]
  arr.each do |v|
    a_order[v[1].to_i - 1].push(v[0])
  end
  a_order
end

len = gets.to_i
arr = gets.split(' ')
o = calc_a_order arr

arr1 = arr.dup
0.upto(len-2) do |i|
  (len-1).downto(i+1) do |j|
    arr1[j], arr1[j-1] = arr1[j-1], arr1[j] if arr1[j][1].to_i <  arr1[j-1][1].to_i
  end
end
puts arr1.join(' ')

o1 = calc_a_order arr1
puts (o == o1) ? 'Stable' : 'Not Stable'

arr2 = arr.dup
0.upto(len-2) do |i|
  minj = i
  (i+1).upto(len-1) do |j|
    minj = j if arr2[minj][1].to_i > arr2[j][1].to_i
  end
  arr2[i], arr2[minj] = arr2[minj], arr2[i]
end
puts arr2.join(' ')

o2 = calc_a_order arr2
puts (o == o2) ? 'Stable' : 'Not stable'
