
def selection(arr)
  n = arr.length
  for i in 0...n
    mini = i
    for j in i...n
      if arr[j][1] < arr[mini][1]
        mini = j
      end
    end
    if i != mini
      arr[i], arr[mini] = arr[mini], arr[i]
    end
  end
  return arr
end
def bubble(arr)
  n = arr.length
  for i in 0...n
    for j in 1..(n - i - 1)
      if arr[n - j][1] < arr[n - j - 1][1]
        arr[n - j], arr[n - j - 1] = arr[n - j - 1], arr[n - j]
      end
    end
  end
  return arr
end
gets.to_i
arr = gets.split(" ").map{|item|item.split(//)}
bub = bubble(arr.dup)
sel = selection(arr.dup)
i = 0
arr.sort_by!{|a|[a[1], i += 1]}
puts bub.map(&:join).join(" ")
if bub == arr
  puts "Stable"
else
  puts "Not stable"
end
puts sel.map(&:join).join(" ")
if sel == arr
  puts "Stable"
else
  puts "Not stable"
end