class Card
  def initialize(str)
    tmp = str.split("")
    @mark = tmp[0]
    @number = tmp[1].to_i
  end

  def description
    "#{@mark}#{@number}"
  end

  attr_reader :mark, :number
end

def bubble_sort(c, n)
  0.upto(n-1).each {|i|
    (n-1).downto(i+1).each {|j|
      if c[j].number < c[j-1].number
        c[j], c[j-1] = c[j-1], c[j]
      end
    }
  }
  c
end

def selection_sort(c, n)
  0.upto(n-1).each {|i|
    minj = i
    i.upto(n-1).each {|j|
      minj = j if c[j].number < c[minj].number
    }
    c[i], c[minj] = c[minj], c[i]
  }
  c
end

def extract_duplicate(cards)
  dups = cards.group_by{|c| c.number}.reject{|k,v| v.one?}
  dups.keys.sort.map {|k| dups[k].map(&:description)}
end

def is_stable?(org_dup, other_dup)
  p org_dup
  p other_dup
  org_dup == other_dup ? "Stable" : "Not stable"
end

n = gets.to_i
cards = gets.split(" ").map {|x| Card.new x}
o_dup = extract_duplicate cards

bs = bubble_sort cards.dup, n
ss = selection_sort cards.dup, n

bs_dup = extract_duplicate bs
ss_dup = extract_duplicate ss

puts bs.map(&:description).join(" ")
puts is_stable? o_dup, bs_dup
puts ss.map(&:description).join(" ")
puts is_stable? o_dup, ss_dup