def bubble_sort(array, n)
  n.times do |i|
    (n - 1).downto(i + 1) do |j|
      if array[j].num < array[j - 1].num
        array[j], array[j - 1] = array[j - 1], array[j]
      end
    end
  end
  array
end

def selection_sort(array, n)
  n.times do |i|
    minj = i
    i.upto(n - 1) do |j|
      minj = j if array[j].num < array[minj].num
    end
    array[i], array[minj] = array[minj], array[i]
  end
  array
end

# 安定化どうか判定 バブルソートと比較して判定
def stable?(bubble, sorted)
  bubble.each_with_index do |element, index|
    return false if element.mark != sorted[index].mark
  end
  true
end

class Card
  def initialize(mark, num)
    @mark = mark
    @num = num
  end
  attr_accessor :mark, :num

  def to_s
    @mark + @num
  end
end

n = gets.to_i
cards = gets.split(' ').map do |card|
  Card.new(card[0], card[1])
end
cards2 = cards.clone
bubble = bubble_sort(cards, n)
selection = selection_sort(cards2, n)

puts bubble.map(&:to_s).join(' ')
puts 'Stable'
puts selection.map(&:to_s).join(' ')
if stable? bubble, selection
  puts 'Stable'
else
  puts 'Not stable'
end

