sig
  val pi : float
  exception Timeout of string
  type ('a, 'b) choice = Left of 'a | Right of 'b
  module Strings :
    sig
      type elt = string
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val max_elt : t -> elt
      val choose : t -> elt
      val split : elt -> t -> t * bool * t
    end
  val add_strings : string list -> Aux.Strings.t -> Aux.Strings.t
  val strings_of_list : string list -> Aux.Strings.t
  module Ints :
    sig
      type elt = int
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val max_elt : t -> elt
      val choose : t -> elt
      val split : elt -> t -> t * bool * t
    end
  val add_ints : int list -> Aux.Ints.t -> Aux.Ints.t
  val ints_of_list : int list -> Aux.Ints.t
  module StrMap :
    sig
      type key = string
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> 'a -> 'a t -> 'a t
      val singleton : key -> 'a -> 'a t
      val remove : key -> 'a t -> 'a t
      val merge :
        (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
      val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
      val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> 'a -> unit) -> 'a t -> unit
      val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
      val for_all : (key -> 'a -> bool) -> 'a t -> bool
      val exists : (key -> 'a -> bool) -> 'a t -> bool
      val filter : (key -> 'a -> bool) -> 'a t -> 'a t
      val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
      val cardinal : 'a t -> int
      val bindings : 'a t -> (key * 'a) list
      val min_binding : 'a t -> key * 'a
      val max_binding : 'a t -> key * 'a
      val choose : 'a t -> key * 'a
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val map : ('a -> 'b) -> 'a t -> 'b t
      val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    end
  val strmap_of_assoc : (string * 'a) list -> 'a Aux.StrMap.t
  val strmap_filter :
    (string -> 'a -> bool) -> 'a Aux.StrMap.t -> (string * 'a) list
  module IntMap :
    sig
      type key = int
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> 'a -> 'a t -> 'a t
      val singleton : key -> 'a -> 'a t
      val remove : key -> 'a t -> 'a t
      val merge :
        (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
      val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
      val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> 'a -> unit) -> 'a t -> unit
      val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
      val for_all : (key -> 'a -> bool) -> 'a t -> bool
      val exists : (key -> 'a -> bool) -> 'a t -> bool
      val filter : (key -> 'a -> bool) -> 'a t -> 'a t
      val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
      val cardinal : 'a t -> int
      val bindings : 'a t -> (key * 'a) list
      val min_binding : 'a t -> key * 'a
      val max_binding : 'a t -> key * 'a
      val choose : 'a t -> key * 'a
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val map : ('a -> 'b) -> 'a t -> 'b t
      val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    end
  val intmap_of_assoc : (int * 'a) list -> 'a Aux.IntMap.t
  val intmap_filter :
    (int -> 'a -> bool) -> 'a Aux.IntMap.t -> (int * 'a) list
  module BasicOperators :
    sig
      val ( -| ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b
      val ( <| ) : ('a -> 'b) -> 'a -> 'b
    end
  val int_pow : int -> int -> int
  val fst3 : 'a * 'b * 'c -> 'a
  val snd3 : 'a * 'b * 'c -> 'b
  val trd3 : 'a * 'b * 'c -> 'c
  val map_fst : ('a -> 'b) -> 'a * 'c -> 'b * 'c
  val map_snd : ('a -> 'b) -> 'c * 'a -> 'c * 'b
  val random_elem : 'a list -> 'a
  val concat_map : ('a -> 'b list) -> 'a list -> 'b list
  val map_prepend : 'a list -> ('b -> 'a) -> 'b list -> 'a list
  val map_rev_prepend : 'a list -> ('b -> 'a) -> 'b list -> 'a list
  val map_some : ('a -> 'b option) -> 'a list -> 'b list
  val find_some : ('a -> 'b option) -> 'a list -> 'b
  val map_reduce :
    ('a -> 'b * 'c) -> ('d -> 'c -> 'd) -> 'd -> 'a list -> ('b * 'd) list
  val collect : ('a * 'b) list -> ('a * 'b list) list
  val repeating_key_sorted : ('a * 'b) list -> bool
  val concat_foldr : ('a -> 'b -> 'b list) -> 'a list -> 'b list -> 'b list
  val concat_foldl : ('a -> 'b -> 'b list) -> 'a list -> 'b list -> 'b list
  val list_rev_split :
    ?acc1:'a list -> ?acc2:'b list -> ('a * 'b) list -> 'a list * 'b list
  val list_remove : 'a -> 'a list -> 'a list
  val list_diff : 'a list -> 'a list -> 'a list
  val sorted_diff : 'a list -> 'a list -> 'a list
  val list_inter : 'a list -> 'a list -> 'a list
  val list_init : (int -> 'a) -> int -> 'a list
  val sorted_inter : 'a list -> 'a list -> 'a list
  val sorted_merge : 'a list -> 'a list -> 'a list
  val merge :
    ?sorted:bool ->
    cmp:('a -> 'a -> int) ->
    merge:('a -> 'a -> 'a) -> 'a list -> 'a list -> 'a list
  val sorted_multiset_union :
    ('a * int) list -> ('a * int) list -> ('a * int) list
  val rev_assoc : ('a * 'b) list -> 'b -> 'a
  val mem_rev_assoc : ('a * 'b) list -> 'b -> bool
  val rev_assoc_all : ('a * 'b) list -> 'b -> 'a list
  val assoc_all : 'a -> ('a * 'b) list -> 'b list
  val replace_assoc : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list
  val pop_assoc : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
  val pop_assq : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
  val update_assoc :
    'a -> 'b -> ('b -> 'b) -> ('a * 'b) list -> ('a * 'b) list
  val cons : 'a -> 'a list -> 'a list
  val some : 'a -> 'a option
  val unsome : 'a option -> 'a
  val list_of_opt : 'a option -> 'a list
  val map_try : ('a -> 'b) -> 'a list -> 'b list
  val find_try : ('a -> 'b) -> 'a list -> 'b
  val fold_left_try : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
  val array_foldi_left : (int -> 'a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  val power :
    ?timeout:(unit -> bool) -> 'a list -> 'b list -> ('a * 'b) list list
  val product :
    ?upto:int -> ?timeout:(unit -> bool) -> 'a list list -> 'a list list
  val product_size : 'a list list -> int
  val pairs : 'a list -> ('a * 'a) list
  val all_ntuples : ?timeout:(unit -> bool) -> 'a list -> int -> 'a list list
  val all_subsets : ?max_size:int -> 'a list -> 'a list list
  val remove_one : 'a -> 'a list -> 'a list
  val remove_last : 'a list -> 'a list
  val insert_nth : int -> 'a -> 'a list -> 'a list
  val find_index : 'a -> 'a list -> int
  val pop_find : ('a -> bool) -> 'a list -> 'a * 'a list
  val maximal : ('a -> 'a -> bool) -> 'a list -> 'a list
  val maximal_o : ('a -> 'a -> bool) -> 'a list -> 'a
  val maximal_unique : ('a -> 'a -> bool) -> 'a list -> 'a list
  val add_to_maximal : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list
  type 'a topol_sort_ops = {
    rem_edge : 'a -> 'a -> unit;
    iter_outgoing : ('a -> unit) -> 'a -> unit;
    no_incoming : 'a -> bool;
    node_to_string : 'a -> string;
  }
  val topol_sort : 'a Aux.topol_sort_ops -> 'a list -> 'a list
  val unique_sorted : ?cmp:('a -> 'a -> int) -> 'a list -> 'a list
  val unique_append : 'a list -> 'a list -> 'a list
  val unique : ('a -> 'a -> bool) -> 'a list -> 'a list
  val not_unique : 'a list -> bool
  val take_n : int -> 'a list -> 'a list
  val take_n_with_rest : int -> 'a list -> 'a list * 'a list
  val range : ?from:int -> int -> int list
  val array_from_assoc : (int * 'a) list -> 'a array
  val array_map_some : ('a -> 'b option) -> 'a array -> 'b array
  val array_mapi_some : (int -> 'a -> 'b option) -> 'a array -> 'b array
  val array_map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
  val array_fold_left2 :
    ('a -> 'b -> 'c -> 'a) -> 'a -> 'b array -> 'c array -> 'a
  val array_fold_map2 :
    ('a -> 'b -> 'c -> 'a * 'd) ->
    'a -> 'b array -> 'c array -> 'a * 'd array
  val array_combine : 'a array -> 'b array -> ('a * 'b) array
  val array_exists : ('a -> bool) -> 'a array -> bool
  val array_existsi : (int -> 'a -> bool) -> 'a array -> bool
  val array_mem : 'a -> 'a array -> bool
  val array_map_of_list : ('a -> 'b) -> 'a list -> 'b array
  val array_argfind : ('a -> bool) -> 'a array -> int
  val array_argfindi : (int -> 'a -> bool) -> 'a array -> int
  val array_find_all : ('a -> bool) -> 'a array -> 'a list
  val array_argfind_all : ('a -> bool) -> 'a array -> int list
  val array_for_all : ('a -> bool) -> 'a array -> bool
  val array_for_alli : (int -> 'a -> bool) -> 'a array -> bool
  val array_for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
  val array_iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
  val array_replace : 'a array -> int -> 'a -> 'a array
  val list_find_all_max : ('a -> 'a -> int) -> 'a list -> 'a list
  val array_find_all_max : ('a -> 'a -> int) -> 'a array -> 'a list
  val array_argfind_all_max : ('a -> 'a -> int) -> 'a array -> int list
  val neg : ('a -> bool) -> 'a -> bool
  val is_right : ('a, 'b) Aux.choice -> bool
  val partition_choice : ('a, 'b) Aux.choice list -> 'a list * 'b list
  val partition_map :
    ('a -> ('b, 'c) Aux.choice) -> 'a list -> 'b list * 'c list
  val map_choice :
    ('a -> 'b) -> ('c -> 'd) -> ('a, 'c) Aux.choice -> ('b, 'd) Aux.choice
  val map_option : ('a -> 'b) -> 'a option -> 'b option
  val omap : 'b -> ('a -> 'b) -> 'a option -> 'b
  val transpose_lists : 'a list list -> 'a list list
  val fold_n : ('a -> 'a) -> 'a -> int -> 'a
  val not_conflicting_name :
    ?truncate:bool -> Aux.Strings.t -> string -> string
  val not_conflicting_names :
    ?truncate:bool -> string -> Aux.Strings.t -> 'a list -> string list
  val list_fprint :
    (Pervasives.out_channel -> 'a -> unit) ->
    Pervasives.out_channel -> 'a list -> unit
  val array_fprint :
    (Pervasives.out_channel -> 'a -> unit) ->
    Pervasives.out_channel -> 'a array -> unit
  val fprint_sep_list :
    ?newline:int ->
    string ->
    (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a list -> unit
  val is_uppercase : char -> bool
  val is_lowercase : char -> bool
  val is_digit : char -> bool
  val is_letter : char -> bool
  val is_alphanum : char -> bool
  val is_space : char -> bool
  val clean_name : string -> string
  val strip_charprop : (char -> bool) -> string -> string
  val strip_spaces : string -> string
  val split_charprop :
    ?keep_split_chars:bool -> (char -> bool) -> string -> string list
  type split_result = Text of string | Delim of string
  val split_chars_after :
    char -> char list -> string -> Aux.split_result list
  val split_spaces : string -> string list
  val split_newlines : string -> string list
  val split_empty_lines : string -> string list
  val normalize_spaces : string -> string
  val replace_charprop : (char -> bool) -> string -> string -> string
  val str_index : ?from:int -> string -> string -> int
  val str_contains : string -> string -> bool
  val str_subst_once : string -> string -> string -> string
  val str_subst_all : string -> string -> string -> string
  val str_subst_once_from_to : string -> string -> string -> string -> string
  val str_subst_all_from_to : string -> string -> string -> string -> string
  module type PRIOQUEUE =
    sig
      type 'a t
      val make_empty : leq:('a -> 'a -> bool) -> 'a Aux.PRIOQUEUE.t
      val of_list : leq:('a -> 'a -> bool) -> 'a list -> 'a Aux.PRIOQUEUE.t
      val insert : 'a Aux.PRIOQUEUE.t -> 'a -> 'a Aux.PRIOQUEUE.t
      val peek : 'a Aux.PRIOQUEUE.t -> 'a
      val extract : 'a Aux.PRIOQUEUE.t -> 'a * 'a Aux.PRIOQUEUE.t
      val map :
        leq:('b -> 'b -> bool) ->
        monotone:('a -> 'b) -> 'a Aux.PRIOQUEUE.t -> 'b Aux.PRIOQUEUE.t
      exception Queue_is_empty
      val is_empty : 'a Aux.PRIOQUEUE.t -> bool
    end
  module SimplePrioQueue : PRIOQUEUE
  module LeftistPrioQueue : PRIOQUEUE
end