
let split str delim =
  let rec doit s acc =
    match
      try Some (String.index s delim)
      with _ -> None
    with
    | None -> List.rev (s :: acc)
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s2 (s1 :: acc)
  in
  doit str []

let print_array a =
  Array.iteri (fun i s -> Printf.printf (if i = 0 then "%s" else " %s") s) a;
  print_newline ()

let bubble_sort a n cmp =
  let rec bubble j flag =
    if j <= 0 then flag
    else begin
      if cmp a.(j - 1) a.(j) <= 0 then bubble (j - 1) flag
      else begin
        let tmp = a.(j) in a.(j) <- a.(j - 1); a.(j - 1) <- tmp;
        bubble (j - 1) true
      end
    end
  in
  let rec doit flag =
    if not flag then ()
    else doit (bubble (n - 1) false)
  in
  doit true

let selection_sort a n cmp =
  let rec select j minj =
    if j >= n then minj
    else select (j + 1) (if cmp a.(j) a.(minj) < 0 then j else minj)
  in
  let rec doit i =
    if i >= n then ()
    else begin
      let minj = select i i in
      if minj <> i then begin
        let tmp = a.(i) in
        a.(i) <- a.(minj);
        a.(minj) <- tmp;
      end;
      doit (i + 1)
    end
  in
  doit 0

let cmp_card x y =
  let num_of_char c = Char.code c - Char.code '0' in
  compare (num_of_char x.[1]) (num_of_char y.[1])

let stable_p a b n =
  let rec doit i =
    if i >= n then true
    else if a.(i) <> b.(i) then false
    else doit (i + 1)
  in
  doit 0

let () =
  let n = read_int () in
  let a = Array.of_list (split (read_line ()) ' ') in
  let b = Array.copy a in
  bubble_sort a n cmp_card;
  selection_sort b n cmp_card;
  print_array a;
  Printf.printf "Stable\n";
  print_array b;
  Printf.printf (if stable_p a b n then "Stable\n" else "Not stable\n")