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
  while 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
end