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 = float_of_int
let i2f = int_of_float

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


module ToyList = 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 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 = ToyList


module ToyString = 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 = ToyString

let spsp s = S.split_on_char ' ' s

module ToySortedSet (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

module Ss = ToySortedSet

module ToySortedMap = struct
  include Map

  let nmem x st = not @@ mem x st

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

module Ms = ToySortedMap


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 [[]]



module ToyGraph (V : Set.OrderedType) = struct

  module Vset = Ss(V)

  type t = { vs : Vset.t; nb : (V.t, Vset.t) Ms.t }

  let veq u v = V.compare u v = 0
  let vneq u v = V.compare u v <> 0

  let nothing = { vs = Vset.empty; nb = Ms.empty }

  let add_edge (e : V.t * V.t) g =
    let (v1, v2) = e in
    let vs1 = g.vs |> Vset.add v1 |> Vset.add v2 in
    let nbvs = g.nb |> Ms.get_or v1 Vset.empty in
    let nb1 = g.nb |> Ms.add v1 (nbvs |> Vset.add v2) in
    { vs = vs1; nb = nb1 }

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

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

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


  let nbiter (upd : V.t -> V.t -> t -> t * bool)
    (u : V.t) (fr : Vset.t) (cls : Vset.t) (g : t) =
    let nb = g.nb |> Ms.get u in
    nb |> Vset.foldl (fun (ga, nxfr, nxcls) v ->
      if vneq u v || Vset.mem v nxcls then
        (ga, nxfr, nxcls)
      else
        let (gu, close) = upd u v ga in
        (gu,
          Vset.add v nxfr,
          if close then Vset.add v nxcls else nxcls)
    ) (g, fr, cls)

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

    let rec progress fr cls g' =
      let (v, fr') = Vset.pop_min fr in
      let (gu, nxfr, nxcls) = nbiter upd v 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 : Vset.t) (g : t) =

    let rec progress fr cls g' =
      let (gu, nxfr, nxcls) =
        fr |> Vset.foldl (fun (ga, nxfra, nxclsa) v ->
          nbiter upd v nxfra nxclsa ga
        ) (g', fr, 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


module ToyIntArithmetic = struct

  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

end

module N = ToyIntArithmetic


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 ToyMatrix = struct
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

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

module G = ToyGraph(struct
  type t = int * int
  let compare (x1, y1) (x2, y2) = compare x1 x2
  end)

let _ =
  let s = rds () in
  puts @@ S.left s 3
;;


Measured memory_bytes: 5396