n = gets.to_i
nums = gets.split

bub_nums = nums.clone
bub_count = 0
for c in 0..(n-2) do #01234
  for d in 0..n-c-2 do #0=>0123 1=>012 3=>0
    if bub_nums[d][1].to_i > bub_nums[d+1][1].to_i
      bub_nums[d], bub_nums[d+1] = bub_nums[d+1], bub_nums[d]
      bub_count += 1
    end
  end
end
puts bub_nums.join(" ")
puts "Stable"

sel_nums = nums
sel_count = 0
for i in 0..n-2
  minid = i
  for k in i..n-1 do
    if sel_nums[minid][1].to_i > sel_nums[k][1].to_i
      minid = k
    end
  end
  #print i != minid
  if i != minid
    sel_nums[minid], sel_nums[i] = sel_nums[i], sel_nums[minid]
    sel_count += 1
  end
  #puts nums.join(" ")
end
puts sel_nums.join(" ")

if sel_nums == bub_nums
  puts "Stable"
else
  puts "Not stable"
end
