def bubble_sort(a, n)
  1.upto(n-1) do |i|
    (n-1).downto(i) do |j|
      if a[j-1] > a[j]
        a[j-1], a[j] = a[j], a[j-1]
        count += 1
      end
    end
  end
  a
end

def selection_sort(a, n)
  a.each.with_index do |x, i|
    break if i == n - 1
    mini = [a[i+1..n-1].min, x].min
    if mini < x
      mini_i = a[i+1..n-1].index(mini) + (i+1)
      a[i], a[mini_i] = mini, x
      count += 1
    end
  end
  a
end

puts a.join(' '), count

n = gets.to_i
a = gets.chomp.split
an = a.map{ |x| x.slice(1,1).map(&:to_i) }

puts bubble_sort(a, n), "Stable", selection_sort(a, n), "Stable"