# input: H4 C9 S4 D2 C3
# return: [["H", 4], ["C", 9], ["S", 4], ["D", 2], ["C", 3]]
gets
a = gets.rstrip.split.map{|e| e.split('')}.map{|e| [e[0], e[1].to_i]}

def bubble_sort(a)
  is_reverse = true
  while is_reverse
    is_reverse = false
    0.upto(a.size - 2) do | i |
      if a[i][1] > a[i+1][1]
        a[i], a[i+1] = a[i+1], a[i]
        is_reverse = true
      end
    end
  end
  return a
end

def selection_sort(a)
  0.upto(a.size - 1) do | i |
    min_j = i
    i.upto(a.size - 1) do | j |
      if a[j][1] < a[min_j][1]
        min_j = j
      end
    end
    a[min_j], a[i] = a[i], a[min_j]
  end
  return a
end

def is_stable?(a, b)
  duplicate = []
  before = b[0][1]
  1.upto(b.size - 1) do | i |
    duplicate << before if before == b[i][1]
    before = b[i][1]
  end
  duplicate.uniq!

  duplicate.each do | d |
    dup_a, dup_b = [], []
    a.each do | ae |
      if ae[1] == d
        dup_a << ae
      end
    end
    b.each do | be |
      if be[1] == d
        dup_b << be
      end
    end
    return false if dup_a != dup_b
  end
  return true
end

bubbled =  bubble_sort(a.clone)
puts bubbled.map{|e|e.join('')}.join(' ')
puts is_stable?(a, bubbled) ? 'Stable' : 'Not stable'

selected = selection_sort(a.clone)
puts selected.map{|e|e.join('')}.join(' ')
puts is_stable?(a, selected) ? 'Stable' : 'Not stable'

