let rec find a x n =
  if a.(n) = x then n else find a x (n+1);;

let print_array l =
  Array.fold_left (fun x y -> (if x = "" then "" else x^" ")^y) "" l |> print_endline;;

let to_array s = Str.split (Str.regexp_string " ") s |> Array.of_list;;

let bubble_sort c n =
  let b = Array.copy c in
  for i = 0 to n-1 do
    for j = n-1 downto i+1 do
      if Char.code b.(j).[1] < Char.code b.(j-1).[1] then
        let temp = b.(j) in
        b.(j) <- b.(j-1);b.(j-1) <-temp;
    done;
  done;
  b;;

let selection_sort c n =
  let b = Array.copy c in
  for i = 0 to n-1 do
    let minj = ref i in
    for j = i to n-1 do
      if Char.code b.(j).[1] < Char.code b.(!minj).[1] then
        minj := j
    done;
    let temp = b.(i) in
    b.(i) <- b.(!minj);b.(!minj) <- temp;
  done;
  b;;

let is_stable org c n =
  let rec loop = function
      i when i = n -> "Stable"
    | i ->
       if (Char.code c.(i).[1]) = (Char.code c.(i-1).[1]) then
         if find org c.(i) 0 > find org c.(i-1) 0 then loop (i+1)
         else "Not stable"
       else
         loop (i+1)
  in loop 1
;;

let () =
  let n = read_int() and
      a = read_line () |> to_array in
  let b = bubble_sort a n and
      s = selection_sort a n in
  let r1 = is_stable a b n and
      r2 = is_stable a s n in
  print_array b;
  print_endline r1;
  print_array s;
  print_endline r2
;;