let bubble_sort ?(comparator=compare) a n =
  let rec loop () =
    let rec bubble c = function
      | 0 -> c
      | i ->
        bubble
          (match comparator a.(i) a.(i-1) with
           -1 -> (let aj = a.(i-1) in a.(i-1) <- a.(i); a.(i) <- aj; c+1)
           | _ -> c)
          (i-1)
    in
    match bubble 0 (n-1) with
      0 -> a
    | _ -> loop ()
  in loop ()

let selection_sort ?(comparator=compare) a n =
  let rec selection j acc =
    match j < n with
      true ->
      selection (j+1) (match comparator a.(j) a.(acc) with -1 -> j | _ -> acc)
    | false -> acc
  in
  let rec loop = function
      i when i = n -> a
    | i ->
      (match selection (i+1) i with
       | j when i != j -> let ai = a.(i) in a.(i) <- a.(j); a.(j) <- ai
       | _ -> ());
      loop (i+1)
  in
  loop 0

let () =
  let n = read_int () in
  let l = read_line () |> Str.split (Str.regexp " ")
          |> List.mapi (fun i x -> i,x) in
  let comp (_,a) (_,b) = compare a.[1] b.[1] in
  let is_stable = ref true in
  let print_array_b a =
    Array.iteri (fun i x ->
        Printf.printf
          (match i with i when i=n-1 -> "%s\nStable\n" | _ -> "%s ")
          (snd x))
      a in
  let print_array_s a =
    Array.iteri (fun i x ->
        Printf.printf
          (match i with
             i when i=n-1 ->
             (if !is_stable then "%s\nStable\n" else  "%s\nNot stable\n")
           | i ->
             (if snd a.(i) = snd a.(i+1) && fst a.(i) > fst a.(i+1)
              then is_stable := false);
             "%s ")
          (snd x))
      a in  
  print_array_b (bubble_sort ~comparator:comp (Array.of_list l) n);
  print_array_s (selection_sort ~comparator:comp (Array.of_list l) n)