class Card
  def initialize(s)
    @suit = s[0]
    @num = s[1].to_i
  end
  def suit
    return @suit
  end
  def num
    return @num
  end
  def val
    return @suit + @num.to_s
  end
end

def bubbleSort(a,n)
  for i in 0..n-1 do
    for j in (i+1..n-1).to_a.reverse
      if a[j].num < a[j-1].num
        a[j],a[j-1] = a[j-1],a[j]
      end
    end
  end
end

def selectionSort(a,n)
  for i in 0..n-1 do
    minj = i
    for j in i..n-1 do
      if a[j].num < a[minj].num
        minj = j
      end
    end
    if i != minj
      a[i],a[minj] = a[minj],a[i]
    end
  end
end

def isStable(a,b,n)
  for ai in 0..n-2 do
    for bi in 1..n-1 do
      if a[ai]!=b[bi]
        next
      end
      for aj in ai+1..n-1 do
        if a[ai].num!=a[aj].num
          next
        end
        for bj in 0..bi-1 do
          if a[aj]==b[bj]
            return "Not stable"
          end
        end
      end
    end
  end
  return "Stable"
end 

n = gets.chomp.to_i
cards = gets.chomp.split(" ").map{|x| Card.new(x)}
cards_bubble = cards.clone
cards_selection = cards.clone
bubbleSort(cards_bubble,n)
selectionSort(cards_selection,n)
printf("%s\n", cards_bubble.map{|x| x.val}.join(" "))
printf("%s\n", isStable(cards,cards_bubble,n))
printf("%s\n", cards_selection.map{|x| x.val}.join(" "))
printf("%s\n", isStable(cards,cards_selection,n))
