open Batteries
open Printf

let ($) g f x = g (f x)

let swap = Tuple2.swap

let s2i = int_of_string
let i2s = string_of_int
let s2f = float_of_string
let f2s = string_of_float
let c2i = int_of_char
let i2c = char_of_int
let f2i = int_of_float
let i2f = float_of_int 

let c2s = String.of_char
let s2cl = String.to_list
let cl2s = String.of_list

let puts s = print_endline s
let putyn b = puts (if b then "Yes" else "No")
let puti i = puts @@ i2s i

let rep lb bnd ub f = match bnd with
  | `To -> for i = lb to ub do f i done
  | `Til -> for i = lb to (ub - 1) do f i done

let rep2 lb1 bnd1 ub1 () lb2 bnd2 ub2 f = 
  match (bnd1, bnd2) with
  | (`To, `To) -> for i = lb1 to ub1 do for j = lb2 to ub2 do f i j done done
  | (`To, `Til) -> for i = lb1 to ub1 do for j = lb2 to (ub2 - 1) do f i j done done
  | (`Til, `To) -> for i = lb1 to (ub1 - 1) do for j = lb2 to ub2 do f i j done done
  | (`Til, `Til) -> for i = lb1 to (ub1 - 1) do for j = lb2 to (ub2 - 1) do f i j done done

module JunkList = struct
  include List

  let nmem x l = not @@ mem x l

  let len = length
  let size = length
  let nempty l = not @@ is_empty l

  let hdop l = if nempty l then Some (hd l) else None

  (* let taker = drop *)
  let takewh = take_while

  (* let dropr = take *)
  let dropwh = drop_while

  let split_by = span

  let chunk = ntake

  let foldl = fold_left
  let foldli = fold_lefti
  let foldr f z l = fold_right f l z
  let foldri f z l = fold_righti f l z

  let partition_to_map f l =
    foldr (fun x m -> Map.modify_opt (f x) (function
      | None -> Some [x] 
      | Some [] -> Some [x] 
      | Some vl -> Some (x::vl)) m) Map.empty l;;

  (* let scanl = scan_left *)
  (* let scanli = scan_lefti *)
  (* let scanr = scan_right *)
  (* let scanri = scan_righti *)
  
  let flatmap = concat_map

  let zipf = map2
  let zipfi = map2i

end

module L = JunkList

module JunkArray = struct
  include Array 

  let nmem x l = not @@ mem x l

  let len = length
  let size = length
  let is_empty r = len r = 0
  let nempty r = len r > 0

  let take n r = left r n
  let taker n r = right r n

  let takeb x r =
    let l = len r in
    let rec loop i =
      if i >= l then r
      else if r.(i) = x then take i r
      else loop (i + 1)
    in loop 0
     
  (* let takewh = take_while *)

  let drop n r = tail r n
  let dropr n r = take ((len r) - n) r
  (* let dropwh = drop_while *)

  let index_of x r =
    let l = len r in
    let rec loop i =
      if i >= l then None
      else if r.(i) = x then Some i
      else loop (i + 1)
    in loop 0

  (* let split_by = span *)

  (* let chunk = ntake *)

  let foldl = fold_left
  let foldli = fold_lefti
  let foldr f z l = fold_right f l z
  let foldri f z l = fold_righti f l z

  (* let partition_to_map f l = *)
  (*   foldr (fun x m -> Map.modify_opt (f x) (function *)
  (*     | None -> Some [x]  *)
  (*     | Some [] -> Some [x]  *)
  (*     | Some vl -> Some (x::vl)) m) Map.empty l;; *)

  (* let scanl = scan_left *)
  (* let scanli = scan_lefti *)
  (* let scanr = scan_right *)
  (* let scanri = scan_righti *)
  
  let concat2 = append
  
  let flatmap (f : 'a -> 'b array) a =
    map f a |> enum |> L.of_enum |> concat

  let zipf = map2
  (* let zipfi = map2i *)

end

module A = JunkArray

module JunkString = struct
  include String

  let len = length

  let replace_chars = map
  let map = replace

  let maptol f s = L.map f (s2cl s)
  let maptoli f s = L.map f (s2cl s)

  let zipf f a b = L.zipf f (s2cl a) (s2cl b)
  let zipfi f a b = L.zipfi f (s2cl a) (s2cl b)

  let mkstr f sep ls =
    L.foldl (fun acc x -> acc ^ sep ^ (f x)) (f @@ L.hd ls) (List.tl ls)

end

module S = JunkString

let spsp s = S.split_on_char ' ' s


module JunkSortedSet = struct
  include Set

  module Make (Ord : Set.OrderedType) = struct
    include Set.Make(Ord)

    let nmem x st = not @@ mem x st

    let foldl f s z = fold (fun x a -> f a x) z s

    let size = cardinal
  end

  let nmem x st = not @@ mem x st

  let foldl f s z = fold (fun x a -> f a x) z s

  let size = cardinal
end

module Ss = JunkSortedSet

module JunkSortedMap  = struct
  include Map

  module Make (Ord : Map.OrderedType) = struct
    include Map.Make(Ord)

    let nmem x st = not @@ mem x st

    let get = find
    let get_or x d m = find_default d x m

    let size = cardinal
  end

  let nmem x st = not @@ mem x st

  let get = find
  let get_or x d m = find_default d x m

  let size = cardinal
end

module Ms = JunkSortedMap


let set_power ls =
  let rec loop ls pls =
    match ls with
    | [] -> pls
    | hd::tl -> loop tl (L.flatmap (fun p -> [p; hd::p]) pls)
  in loop ls [[]]


exception ArithmeticException of string

module JunkIntArithmetic = struct

  let rec power x e =
    if e = 0 then x
    else 
      let rec loop r x2 e' =
        if e' = 0 then r
        else if e' land 1 = 0 then loop r (x2 * x2) (e' lsr 1)
        else loop (r * x2) (x2 * x2) (e' lsr 1)
      in loop 1 x e

  let rec powers_le_1000 x =
    if x > 32 then [x]
    else
      L.init 9 (fun e -> power x (e + 1))
      |> L.filter (fun y -> y < 1000)

  let primes_le_1000 = [2;3;5;7;11;13;17;19;23;29;31;37;41;
    43;47;53;59;61;67;71;73;79;83;89;97;101;
    103;107;109;113;127;131;137;139;149;151;157;163;167;
    173;179;181;191;193;197;199;211;223;227;229;233;239;
    241;251;257;263;269;271;277;281;283;293;307;311;313;
    317;331;337;347;349;353;359;367;373;379;383;389;397;
    401;409;419;421;431;433;439;443;449;457;461;463;467;
    479;487;491;499;503;509;521;523;541;547;557;563;569;
    571;577;587;593;599;601;607;613;617;619;631;641;643;
    647;653;659;661;673;677;683;691;701;709;719;727;733;
    739;743;751;757;761;769;773;787;797;809;811;821;823;
    827;829;839;853;857;859;863;877;881;883;887;907;911;
    919;929;937;941;947;953;967;971;977;983;991;997]

    let primes_and_powers_le_1000 =
      [2;3;4;5;7;8;9;11;13;16;17;19;23;25;27;29;31;32;37;41;
      43;47;49;53;59;61;64;67;71;73;79;81;83;89;97;
      101;103;107;109;113;121;125;127;128;131;137;139;149;151;
      157;163;167;169;173;179;181;191;193;197;199;211;223;227;
      229;233;239;241;243;251;256;257;263;269;271;277;281;283;
      289;293;307;311;313;317;331;337;343;347;349;353;359;361;
      367;373;379;383;389;397;401;409;419;421;431;433;439;443;
      449;457;461;463;467;479;487;491;499;503;509;512;521;523;
      529;541;547;557;563;569;571;577;587;593;599;601;607;613;
      617;619;625;631;641;643;647;653;659;661;673;677;683;691;
      701;709;719;727;729;733;739;743;751;757;761;769;773;787;
      797;809;811;821;823;827;829;839;841;853;857;859;863;877;
      881;883;887;907;911;919;929;937;941;947;953;961;967;971;
      977;983;991;997]

  let factorize_with ps n =
    let rec loop acc ps e n' =
      if n' <= 1 then ([], n') 
      else
        match ps with
        | [] -> (acc, n')
        | p::t ->
          let r = n' mod p in
          if r = 0 then (
            if n' = p then ((p, e + 1) :: acc, 1)
            else loop acc ps (e + 1) (n' / p)
          ) else
            loop (if e = 0 then acc else (p, e) :: acc) t 0 n'
    in
    let (fs, r) = loop [] ps 0 n in
    (L.rev fs, r)

  let factorize_le_million n =
    factorize_with primes_le_1000 n

  let rec to_bits_le n =
    if n = 0 then []
    else (n mod 2) :: to_bits_le (n lsr 1)

  let rec gcd x y =
    match x mod y with
    | 0 -> y
    | z -> gcd y z

  let ext_euclid a b =
    let rec next (r0, s0, t0) (r1, s1, t1) =
      match r1 with
      | 0 -> (r0, s0, t0)
      | r2 ->
        let q = r0 / r1 in
        next (r1, s1, t1) (r0 - q * r1, s0 - q * s1, t0 - q * t1)
    in
    if a < b then
      let (g, y, x) = next (b, 1, 0) (a, 0, 1) in (g, x, y)
    else
      next (a, 1, 0) (b, 0, 1)

  let modinv x m =
    let (g, y, z) = ext_euclid x m in
    match g with
    | 1 -> y mod m
    | _ -> raise @@ ArithmeticException "Not relatively prime"
      

end

module N = JunkIntArithmetic


module JunkMatrix = struct

  type 'a t = { w : int; h : int; e : 'a array array }

  let make w h e0 =
    { w = w; h = h; e = A.make_matrix w h e0 }

  let from_columns w h e0 elems =
    let matr = make w h e0 in
    elems |> L.iteri (fun j col ->
      col |> L.iteri (fun i x -> matr.e.(i).(j) <- x));
    matr

  let blit (mats, rs, cs, w, h) (matd, rd, cd) =
    rep2 0 `Til w () 0 `Til h (fun i j ->
        matd.e.(rd + i).(cd + j) <- mats.e.(rs + i).(cs + j))

  let expand (w1, h1) (w2, h2) e0 mat =
    let matr = make w2 h2 e0 in
    blit (mat, 0, 0, w1, h1) (matr, 0, 0);
    matr

end

module M = JunkMatrix

module type FieldOps = sig
  type elt
  val zero : elt
  val one : elt
  val neg : elt -> elt
  val rcp : elt -> elt
  val add : elt -> elt -> elt
  val sub : elt -> elt -> elt
  val mul : elt -> elt -> elt
  val div : elt -> elt -> elt
end

module JunkLinearAlgebra (Fop : FieldOps) = struct

  type t = Fop.elt M.t

  let zero w h = M.make w h Fop.zero

  let prod (mat1 : t) (mat2 : t) =
    let matr = zero mat1.w mat2.h in
    rep2 0 `Til mat1.w () 0 `Til mat2.h (fun i j ->
        matr.e.(i).(j) <-
          mat1.e.(i) |> A.foldli (fun
            acc k x -> Fop.add acc (Fop.mul x mat2.e.(k).(i)))
            Fop.zero);
    matr

  exception NotZero of int
  let is_zero (mat : t) =
    try (
      rep 0 `Til mat.w (fun i ->
        if mat.e.(i) |> A.for_all (fun x -> x <> Fop.zero)
          then raise (NotZero 1)
      );
      true
    ) with _ -> false

  let col_addmul c1 (c2, a) (mat : t) =
    rep 0 `Til mat.h (fun i ->
      mat.e.(i).(c1) <- Fop.add mat.e.(i).(c1) (Fop.mul a mat.e.(i).(c2)))

  let col_inner_prod c1 c2 (mat : t) =
    let sum = ref Fop.zero in
    rep 0 `Til mat.h (fun i ->
      sum := Fop.add !sum @@ Fop.mul mat.e.(i).(c1) mat.e.(i).(c2));
    !sum

  (* let orth_extend k0 k1 mat = *)
  (*   let matx = extend (k0, h) ((k0 + k1), h) 0 mat in *)
  (*   rep k0 `Til (k0 + k1) (fun t -> *)
  (*     rep 0 `Til t (fun s ->  *)
  (*       let ip = col_inner_prod s t h matx in *)
  (*       col_addmul t (s, ip) h matx)); *)
  (*   submat (k0, 0) (k0 + k1 - 1, h - 1) matx *)

end

module type OrderedData = sig
  type t
  val compare : t -> t -> int
  val default : t
end

module JunkGraph = struct

  type 'a v_t = int * 'a
  type 'a t = { vs : 'a v_t array; nb : int Ss.t array }

  let empty nv vd =
    let vs0 = Array.make nv (0, vd) in
    for i = 0 to (nv - 1) do vs0.(i) <- (i, vd) done;
    {
      vs = vs0;
      nb = A.make nv Ss.empty
    }

  let add_edge (e : int * int) vd g =
    let (v1, v2) = e in
    g.vs.(v1 - 1) <- (v1, vd);
    g.vs.(v2 - 1) <- (v2, vd);
    g.nb.(v1 - 1) <- g.nb.(v1 - 1) |> Ss.add v2;
    g

  let add_uedge e vd g =
    add_edge e vd (add_edge (swap e) vd g)

  let from_edges nv vd es =
    es |> L.foldl (fun g e -> add_edge e vd g) (empty nv vd)

  let from_uedges nv vd es =
    es |> L.foldl (fun g e -> add_uedge e vd g) (empty nv vd)


end

module G = JunkGraph

module JunkGraphAlgorithms (Vdt : OrderedData) = struct
  
  type t = Vdt.t G.t

  module V = struct
    type t = int * Vdt.t
    let compare (vi1, vd1) (vi2, vd2) =
      let c1 = Vdt.compare vd1 vd2 in
      if c1 = 0 then compare vi1 vi2
      else c1

    let default i = (i, Vdt.default)
    let index (v : t) = fst v
  end

  module Vset = Ss.Make(V)

  let print_vertices label vs =
    printf "%s: " label;
    vs |> Vset.iter (fun (vi, _) -> printf "%d " vi);
    puts ""

  let nbiter (upd : V.t -> V.t -> t -> t * bool)
    (ui : int) (fr : Vset.t) (cls : int Ss.t) (g : t) =
    let nb = g.nb.(ui - 1) in
    let result = nb |> Ss.foldl (fun (ga, nxfr, nxcls) vi ->
    (* puts "nxcls: "; *)
      (* Ss.iter (fun x -> printf "%d " x) nxcls; puts ""; *)
      if ui = vi || Ss.mem vi nxcls then
        (ga, nxfr, nxcls)
      else
        let ue = g.vs.(ui - 1) and ve = g.vs.(vi - 1) in
        let (gu, close) = upd ue ve ga in
        (gu,
          nxfr |> Vset.add ve,
          if close then nxcls |> Ss.add vi else nxcls)
    ) (g, fr, cls)
    in (* puts "";  *)result

  let traverse (upd : V.t -> V.t -> t -> t * bool) 
    (fr0 : Vset.t) (cls0 : int Ss.t) (g : t) =

    let rec progress fr cls g' =
      let (ve, fr') = Vset.pop_min fr in
      let (vi, _) = ve in
      let (gu, nxfr, nxcls) = nbiter upd vi fr' cls g' in
      if Vset.is_empty nxfr then (gu, nxcls)
      else progress nxfr nxcls gu
    in
    progress fr0 cls0 g

  let frontier (upd : V.t -> V.t -> t -> t * bool)
    (fr0 : Vset.t) (cls0 : int Ss.t) (g : t) =

    let rec progress fr cls g' =
      let (gu, nxfr, nxcls) =
        fr |> Vset.foldl (fun (ga, nxfra, nxclsa) ve ->
          let (vi, _) = ve in
          nbiter upd vi nxfra nxclsa ga
        ) (g', Vset.empty, cls)
      in
      if Vset.is_empty nxfr then (gu, nxcls)
      else progress nxfr nxcls gu
    in
    progress fr0 cls0 g

  let bfs (upd : V.t -> V.t -> t -> t) =
    frontier (fun fr cls g' -> (upd fr cls g', true))
  
end


let rds () = read_line ()

let rdi () = s2i @@ rds ()

let rdhs () = spsp @@ rds ()
let rdhi () = rdhs () |> L.map s2i

let rdhf () = rdhs () |> L.map s2f

let rdf2 () = match rdhf () with
| a::b::_ -> (a, b)
| _ -> (0., 0.)

let rdf3 () = match rdhf () with
| a::b::c::_ -> (a, b, c)
| _ -> (0., 0., 0.)

let rdf4 () = match rdhf () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0., 0., 0., 0.)

let rds2 () = match rdhs () with
  | a::b::_ -> (a, b)
  | _ -> ("", "")

let rdi2 () = match rdhi () with
  | a::b::_ -> (a, b)
  | _ -> (0, 0)

let rdi3 () = match rdhi () with
| a::b::c::_ -> (a, b, c)
| _ -> (0, 0, 0)

let rdi4 () = match rdhi () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0, 0, 0, 0)

let rdi5 () = match rdhi () with
| a::b::c::d::e::_ -> (a, b, c, d, e)
| _ -> (0, 0, 0, 0, 0)

let rdv n rf =
  let rec loop n =
    if n <= 0 then []
    else (
      let s = rf () in
      s::(loop (n - 1))
    )
  in loop n

let rdvi n = rdv n rdi
let rdvi2 n = rdv n rdi2
let rdvi3 n = rdv n rdi3
let rdvi4 n = rdv n rdi4


module Galg = JunkGraphAlgorithms (
  struct
    type t = int
    let compare = compare
    let default = 0
  end)

let print_list aa = 
  printf "[ "; aa |> L.iter (fun a -> printf "%d " a); puts "]"

let print_array aa = 
  printf "[ "; aa |> A.iter (fun a -> printf "%d " a); puts "]"

let _ =
  let a = L.hd @@ s2cl @@ rds () in
  puts @@ if Char.is_lowercase a then "a" else "A";

();;


Measured memory_bytes: 5536