def swap(a, i, j)
  tmp = a[j]
  a[j] = a[i]
  a[i] = tmp
  a
end

def bubble_sort(a, n)
  (0..n - 1).each do |i|
    (n - 1).downto(i + 1) do |j|
      a = swap(a, j, j - 1) if a[j][1] < a[j - 1][1]
    end
  end
  puts a.join(' ')
end

def selection_sort(a, n)
  (0..n - 1).each do |i|
    minj = i
    (i..n - 1).each do |j|
      minj = j if a[j][1] < a[minj][1]
    end
    a = swap(a, i, minj)
  end
  puts a.join(' ')
end

def is_stable(a, b, n)
  (0..n - 1).each do |i|
    (i + 1..n - 1).each do |j|
      (0..n - 1).each do |l|
        (l + 1..n - 1).each do |m|
          return false if a[i][1] == a[j][1] && a[i] == b[m] && a[j] == b[l]
        end
      end
    end
  end
  true
end
n = gets.to_i
a = gets.split
b_a = a.dup
s_a = a.dup
bubble_sort(b_a, n)
puts is_stable(a, b_a, n) ? 'Stable' : 'Not stable'
selection_sort(s_a, n)
puts is_stable(a, s_a, n) ? 'Stable' : 'Not stable'

