# 3_5 stable_sort
#ALDS_1_2_C stable_sort

N = gets.to_i
a = gets.split
#
# N = 5
# a = %w(H4 C9 S4 D2 C3)

def bubble_sort(n,a)
  for i in 0..(n-1)
    (n-1).downto(i+1) do |j|
      a[j],a[j-1] = a[j-1],a[j] if a[j][-1] < a[j-1][-1]
    end
  end
end

def selection_sort(n,a)
  for i in 0..(n-1)
    minj = i
    i.upto(n-1) do |j|
      minj = j  if a[minj][-1] > a[j][-1]
    end
    a[i],a[minj] = a[minj],a[i] if a[i] != a[minj]
  end
end

def stable_sorted?(a_in, a_out)
  n = a_in.length
  for i in 0..(n-1)
    for j in (i+1)..(n-1)
      for a in 0..(n-1)
        for b in (a+1)..(n-1)
          if a_in[i][-1] == a_in[j][-1] and
            a_in[i] == a_out[b] and
            a_in[j] == a_out[a]
            return false
          end
        end
      end
    end
  end
  return true
end

b = Marshal.load(Marshal.dump(a))
bubble_sort(N,b)
puts b.join(' ')
puts stable_sorted?(a,b) ? "Stable" : "Not stable"

c = Marshal.load(Marshal.dump(a))
selection_sort(N,c)
puts c.join(' ')
puts stable_sorted?(a,c) ? "Stable" : "Not stable"
