def bubble_sort(a)
  arr = a.dup
  n = arr.length
  for i in 0..n - 1
    j = n - 1
    while j > i
      if arr[j-1][1] > arr[j][1]
        arr[j-1],arr[j] = arr[j],arr[j-1]
      end
      j -= 1
    end
  end
  arr
end
 
def selection_sort(arr)
  a = arr.clone
  for i in 0..(a.length - 1)
    min = i
    for j in i ..(a.length - 1)
      if a[j][1] < a[min][1]
        min = j
      end
    end
    a[i], a[min] = a[min], a[i]
  end
  a
end
 
gets
x = gets.split.map { |v| [v[0], v[1].to_i] }
b = bubble_sort(x)
s = selection_sort(x)
 
puts b.map(&:join).join(' ')
puts 'Stable'
puts s.map(&:join).join(' ')
puts b == s ? 'Stable' : 'Not stable'