def bubble_sort(array)
  length = array.length
  for i in 0..(length-2)
    (length-1).downto(i+1){|j|
      if array[j][1] < array[j-1][1]
        tmp = ""
        tmp = array[j]
        array[j] = array[j-1]
        array[j-1] = tmp
      end
      }
  end
  return array
end

def selection_sort(a)
  n = a.length
  min_index = 0
  (0..n-1).each do |i|
    min_index = i
    (i..n-1).each do |j|
      if a[j][1] < a[min_index][1]
        min_index = j
      end
    end
    if a[min_index][1] < a[i][1]
      tmp = a[i]
      a[i] = a[min_index]
      a[min_index] = tmp
    end
  end
  return a
end

# def selection_sort(array)
#   length = array.length
#   p "before_array = #{array}"
#   for i in 0..(length-1)
#     min = i
#     for j in i..(length-1)
#       p "array = #{array}"
#
#       if array[j][1] < array[min][1]
#         min = j
#       end
#       if array[min][1] <= array[i][1]
#         tmp = ""
#         tmp = array[i]
#         array[i] = array[min]
#         array[min] = tmp
#       end
#     end
#   end
#   return array
# end

# ---------
# def sortBySelection(a, n)
#   n.times do |i|
#     minj = i
#     i.upto(n-1) do |j|
#       minj = j if a[j][1] < a[minj][1]
#     end
#     a[i], a[minj] = a[minj], a[i]
#   end
#   puts a.join(' ')
# end
# --------


def check_stable(bubblesort_array, selectionsort_array)
  bubblesort_array_suits = []
  b_length = bubblesort_array.length
  for i in 0..b_length
    bubblesort_array_suits.push(bubblesort_array[i])
  end
  selectionsort_array_suits = []
  s_length = selectionsort_array.length
  for i in 0..s_length
    selectionsort_array_suits.push(selectionsort_array[i])
  end
  if bubblesort_array_suits == selectionsort_array_suits
    return "Stable"
  else
    return "Not stable"
  end
end

n = gets.chomp.to_i
input_cards = gets.chomp.split.map(&:to_s)
cards = []
for i in 0..(n-1)
  card = input_cards[i].split("")
  card[1] = card[1].to_i
  cards.push(card)
end
cards2 = cards.dup
bubblesort_array = bubble_sort(cards)
selectionsort_array = selection_sort(cards2)
length = bubblesort_array.length
for i in 0..(length-1)
  print bubblesort_array[i][0]
  print bubblesort_array[i][1]
  if i != (length-1)
    print " "
  end
end
print "\n"
puts "Stable"
len = selectionsort_array.length
for i in 0..(len-1)
  print selectionsort_array[i][0]
  print selectionsort_array[i][1]
  if i != (len-1)
    print " "
  end
end
puts "\n"
puts check_stable(bubblesort_array, selectionsort_array)