class Card
  attr_accessor :kind, :number, :first_index

  def initialize(str, index)
    @kind = str[0]
    @number = str[1].to_i
    @first_index = index
  end

  def Card.selection_sort(array)
    0.upto(array.size-1) do |i1|
      i_min = i1
      (i1+1).upto(array.size-1) do |i2|
        if (array[i2].number < array[i_min].number) then
          i_min = i2
        end
      end

      if (i_min != i1) then
        array[i_min], array[i1] = array[i1], array[i_min]
      end
    end
  end

  def Card.bubble_sort(array)
    for i1 in 0...array.size do
      for i2 in i1...array.size-1 do
        index = array.size - 1 - i2 + i1
        if (array[index].number < array[index-1].number) then
          array[index], array[index-1] = array[index-1], array[index]
        end
      end
    end
  end
end

def check_stability(array)
  prev = nil
  array.each do |item|
    if (prev == nil) then
      prev = item
      next
    end

    if (prev.number == item.number) then
      return false if prev.first_index > item.first_index
    end

    prev = item
  end
  return true
end

n = gets.strip.to_i
array = gets.split(' ').each_with_index.map do |item, index|
  Card.new(item, index)
end

array_bub = Array.new(array)
Card.bubble_sort(array_bub)
puts array_bub.map{|x| x.kind + x.number.to_s}.join(' ')

puts (check_stability(array_bub)) ? "Stable" : "Not stable"

array_sel = Array.new(array)
Card.selection_sort(array_sel)
puts array_sel.map{|x| x.kind + x.number.to_s}.join(' ')

puts (check_stability(array_sel)) ? "Stable" : "Not stable"