crd_num = gets(chomp:true).to_i

ary = []
ary = gets().split.map(&:chars)

def stable_sort(n, ary)

  def bubble_sort(n, ary)
    flag = 1
    i = 1
    while flag == 1
      flag = 0
      (n-1).downto(i) do | num |
        if ary[num][1] < ary[num-1][1]
          ary[num], ary[num-1] = ary[num-1], ary[num]
          flag = 1
        end
      end
      i += 1
    end
    ary.map(&:join).join(" ")
  end

  def selection_sort(n, ary)
    n.times do |fix|
      min = fix
      (fix...n).each do |srh|
        if ary[min][1] > ary[srh][1]
          min = srh 
        end
      end
      unless fix == min
        ary[fix], ary[min] = ary[min], ary[fix]
      end
    end
    ary.map(&:join).join(" ")
  end

  ary1 = ary.dup
  b_sort = bubble_sort(n, ary)
  s_sort = selection_sort(n, ary1)

  puts b_sort
  puts "Stable"
  puts s_sort
  puts b_sort == s_sort ? "Stable" : "Not stable"

end

stable_sort(crd_num, ary)
