def bubble_sort(n, a)
  arr = a.clone
  (0...n).each do |i|
    (n-1).downto(i+1) do |j|
      arr[j-1],arr[j] = arr[j],arr[j-1] if arr[j-1][1] > arr[j][1]
    end
  end
  return arr
end
  
def selection_sort(n, a)
  arr = a.clone
  (0...n).each do |i|
    min = i
    (i...n).each do |j|
      min = j if arr[j][1] < arr[min][1]
    end
    arr[i], arr[min] = arr[min], arr[i]
  end
  return arr
end
  
n = gets.to_i
a = gets.split.map { |v| [v[0], v[1].to_i] }
b = bubble_sort(n, a)
s = selection_sort(n, a)
  
puts b.map(&:join).join(' ')
puts 'Stable'
puts s.map(&:join).join(' ')
puts b == s ? 'Stable' : 'Not stable'