let sentinel = ('Z', 1000000001)

let merge_sort a cmp =
  let merge l m r =
    let ni = m - l in
    let nj = r - m in
    let init_ary n p =
      Array.init (n + 1) (fun i -> if i = n then sentinel else a.(p + i))
    in
    let ai = init_ary ni l in
    let aj = init_ary nj m in
    let rec doit i j k =
      if k = r then ()
      else begin
        if cmp ai.(i) aj.(j) <= 0 then (a.(k) <- ai.(i); doit (i + 1) j (k + 1))
        else (a.(k) <- aj.(j); doit i (j + 1) (k + 1))
      end
    in
    doit 0 0 l
  in
  let rec doit llet sentinel = ('Z', 1000000001)

let merge_sort a cmp =
  let merge l m r =
    let ni = m - l in
    let nj = r - m in
    let init_ary n p =
      Array.init (n + 1) (fun i -> if i = n then sentinel else a.(p + i))
    in
    let ai = init_ary ni l in
    let aj = init_ary nj m in
    let rec doit i j k =
      if k = r then ()
      else begin
        if cmp ai.(i) aj.(j) <= 0 then (a.(k) <- ai.(i); doit (i + 1) j (k + 1))
        else (a.(k) <- aj.(j); doit i (j + 1) (k + 1))
      end
    in
    doit 0 0 l
  in
  let rec doit l r =
    if (l + 1) < r then begin
      let m = (l + r) / 2 in
      doit l m;
      doit m r;
      merge l m r
    end
  in
  doit 0 (Array.length a)
 r =
    if (l + 1) < r then begin
      let m = (l + r) / 2 in
      doit l m;
      doit m r;
      merge l m r
    end
  in
  doit 0 (Array.length a)

let quick_sort a cmp =
  let partition p r =
    let x = a.(r) in
    let swap i j =
      let t = a.(i) in a.(i) <- a.(j); a.(j) <- t
    in
    let rec doit i j =
      if j >= r then i
      else begin
        if cmp a.(j) x <= 0 then (swap (i + 1) j; doit (i + 1) (j + 1))
        else doit i (j + 1)
      end
    in
    let i = doit (p - 1) p in
    swap (i + 1) r;
    i + 1
  in
  let rec doit p r =
    if p < r then begin
      let q = partition p r in
      doit p (q - 1);
      doit q r
    end
  in
  doit 0 (Array.length a - 1)

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

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%c %d\n" (fun c d -> (c, d))) in
  let b = Array.copy a in
  merge_sort a (fun (_, x) (_, y) -> compare x y);
  quick_sort b (fun (_, x) (_, y) -> compare x y);
  Printf.printf "%s\n" (if stable_p a b (fun (xc, xd) (yc, yd) -> xc = yc && xd = yd) then "Stable" else "Not stable");
  Array.iter (fun (c, d) -> Printf.printf "%c %d\n" c d) b