def bubblesort(arr_in)
  n = arr_in.length
  for i in 0..n-1
    (i+1..n-1).to_a.reverse.each do |j|
      if arr_in[j][1].to_i < arr_in[j-1][1].to_i
        tmp = arr_in[j]
        arr_in[j] = arr_in[j-1]
        arr_in[j-1] = tmp
      end
    end
  end
end

def selsort(arr_in)
  n = arr_in.length
  for i in 0..n-1
    mini = i
    for j in i..n-1
      if arr_in[j][1].to_i < arr_in[mini][1].to_i
        mini = j
      end
    end
    tmp = arr_in[mini]
    arr_in[mini] = arr_in[i]
    arr_in[i] = tmp
  end
end

if __FILE__ == $0
  num = STDIN.gets.to_i
  tokens = STDIN.gets.chomp!.split
  b_result = Marshal.load(Marshal.dump(tokens))
  bubblesort(b_result)
  puts b_result.join(" ")
  puts "Stable"
  s_result = Marshal.load(Marshal.dump(tokens))
  selsort(s_result)
  puts s_result.join(" ")
  flag = true
  for i in 0..num-1
    if b_result[i] != s_result[i]
      flag = FALSE
    end
  end
  if flag
    puts "Stable"
  else
    puts "Not stable"
  end
end