n = gets.to_i
c = gets.chomp.split

def bubble_sort(c, n)
  0.upto(n-1) do |i|
    (n-1).downto(i+1) do |j|
      if c[j][1].to_i < c[j-1][1].to_i
        c[j],c[j-1] = c[j-1],c[j]
      end
    end
  end
  return c
end

def selection_sort(c, n)
  cnt = 0
  0.upto(n-1) do |i|
    minj = i
    i.upto(n-1) do |j|
      if c[j][1].to_i < c[minj][1].to_i
        minj = j
      end
    end
    c[i], c[minj] = c[minj], c[i]
  end
  return c
end

#Rubyの変数は参照渡しになるのでdupして渡す
b = bubble_sort(c.dup, n)
s = selection_sort(c.dup, n)

#バブルソートは数字が同じとき交換を行わないので常にStable
puts b.join(" "), "Stable"

#バブルソートのソート結果と比較して結果が異なればNot stable
puts s.join(" "), (b == s) ? "Stable" : "Not stable"
