def bubble_sort(n, line)
  n.times do |i|
    trade = 0
    (n-i).times do |j|
      next if line[j+1].nil?

      if line[j][1].to_i > line[j+1][1].to_i
        tmp = line[j]
        line[j] = line[j+1]
        line[j+1] = tmp
        trade += 1
      else
        next
      end
    end
    break if trade == 0
  end

  line
end

def selection_sort(n, line)
  n.times do |i|
    num_line = line.map{ |l| l[1].to_i }
    index = num_line[i..-1].index(num_line[i..-1].min) + i
    next if i == index
  
    tmp = line[i]
    line[i] = line[index]
    line[index] = tmp
  end

  line
end

def stable_state(gets, results)
  gets_dups = []
  results_dups = []

  1.upto(13) do |i|
    gets_dups << gets.select { |g| g[1].to_i == i }
    results_dups << results.select { |r| r[1].to_i == i }
  end

  gets_dups.each_with_index do |g, i|
    return 'Not stable' if g != results_dups[i]
  end

  'Stable'
end

n = gets.to_i
line = gets.split(' ')
bubble_line = line.dup
selection_line = line.dup

bubble = bubble_sort(n, bubble_line)
selection = selection_sort(n, selection_line)

puts bubble.join(' ')
puts stable_state(line, bubble_line)
puts selection.join(' ')
puts stable_state(line, selection_line)
