(* This code extends 'mini_prelude'. *) let FST = (fun v3 -> (match v3 with (Pair (v2, v1)) -> v2)) ;; let SND = (fun v3 -> (match v3 with (Pair (v2, v1)) -> v1)) ;; let CURRY = (fun v1 -> (fun v2 -> (fun v3 -> (v1 (Pair (v2, v3)))))) ;; let UNCURRY = (fun v1 -> (fun v2 -> ((v1 (FST v2)) (SND v2)))) ;; let o = (fun v2 -> (fun v3 -> (fun v1 -> (v2 (v3 v1))))) ;; let I = (fun v1 -> v1) ;; let C = (fun v3 -> (fun v2 -> (fun v1 -> ((v3 v1) v2)))) ;; let K = (fun v2 -> (fun v1 -> v2)) ;; let S = (fun v3 -> (fun v2 -> (fun v1 -> ((v3 v1) (v2 v1))))) ;; let UPDATE = (fun v3 -> (fun v4 -> (fun v2 -> (fun v1 -> (if (v3 = v1) then v4 else (v2 v1)))))) ;; let W = (fun v2 -> (fun v1 -> ((v2 v1) v1))) ;; type one = One ;; type ('a) option = Some of 'a | None ;; let THE = (fun x1 -> (match x1 with None -> (raise (Match_failure (string_of_bool true, 0, 0))) | (Some (v1)) -> v1)) ;; let IS_NONE = (fun v2 -> (match v2 with None -> true | (Some (v1)) -> false)) ;; let IS_SOME = (fun v2 -> (match v2 with None -> false | (Some (v1)) -> true)) ;; let OPTION_MAP = (fun v2 -> (fun v3 -> (match v3 with None -> None | (Some (v1)) -> (Some ((v2 v1)))))) ;; let OPTION_MAP2 = (fun v1 -> (fun v2 -> (fun v3 -> (if ((IS_SOME v2) && (IS_SOME v3)) then (Some (((v1 (THE v2)) (THE v3)))) else None)))) ;; type ('a, 'b) sum = Inr of 'b | Inl of 'a ;; let ISL = (fun v3 -> (match v3 with (Inl (v1)) -> true | (Inr (v2)) -> false)) ;; let ISR = (fun v3 -> (match v3 with (Inl (v1)) -> false | (Inr (v2)) -> true)) ;; let OUTL = (fun x1 -> (match x1 with (Inl (v1)) -> v1 | (Inr (v2)) -> (raise (Match_failure (string_of_bool true, 0, 0))))) ;; let OUTR = (fun x1 -> (match x1 with (Inl (v1)) -> (raise (Match_failure (string_of_bool true, 0, 0))) | (Inr (v2)) -> v2)) ;; let ++ = (fun v3 -> (fun v4 -> (fun v5 -> (match v5 with (Inl (v1)) -> (Inl ((v3 v1))) | (Inr (v2)) -> (Inr ((v4 v2))))))) ;; let rec LENGTH_AUX v3 = (fun v4 -> (match v3 with Nil -> v4 | (Cons (v2, v1)) -> ((LENGTH_AUX v1) (v4 + 1)))) ;; let LENGTH = (fun v1 -> ((LENGTH_AUX v1) 0)) ;; let rec MAP v3 = (fun v4 -> (match v4 with Nil -> Nil | (Cons (v2, v1)) -> (Cons ((v3 v2), ((MAP v3) v1))))) ;; let rec FILTER v3 = (fun v4 -> (match v4 with Nil -> Nil | (Cons (v2, v1)) -> (if (v3 v2) then (Cons (v2, ((FILTER v3) v1))) else ((FILTER v3) v1)))) ;; let rec FOLDR v3 = (fun v4 -> (fun v5 -> (match v5 with Nil -> v4 | (Cons (v2, v1)) -> ((v3 v2) (((FOLDR v3) v4) v1))))) ;; let rec FOLDL v3 = (fun v4 -> (fun v5 -> (match v5 with Nil -> v4 | (Cons (v2, v1)) -> (((FOLDL v3) ((v3 v4) v2)) v1)))) ;; let rec SUM v3 = (match v3 with Nil -> 0 | (Cons (v2, v1)) -> (v2 + (SUM v1))) ;; let rec UNZIP v3 = (match v3 with Nil -> (Pair (Nil, Nil)) | (Cons (v2, v1)) -> (Pair ((Cons ((FST v2), (FST (UNZIP v1)))), (Cons ((SND v2), (SND (UNZIP v1))))))) ;; let rec FLAT v3 = (match v3 with Nil -> Nil | (Cons (v2, v1)) -> ((APPEND v2) (FLAT v1))) ;; let rec TAKE v3 = (fun v4 -> (match v4 with Nil -> Nil | (Cons (v2, v1)) -> (if (v3 <= 0) then Nil else (Cons (v2, ((TAKE (v3 - 1)) v1)))))) ;; let rec DROP v3 = (fun v4 -> (match v4 with Nil -> Nil | (Cons (v2, v1)) -> (if (v3 <= 0) then (Cons (v2, v1)) else ((DROP (v3 - 1)) v1)))) ;; let rec SNOC v3 = (fun v4 -> (match v4 with Nil -> (Cons (v3, Nil)) | (Cons (v2, v1)) -> (Cons (v2, ((SNOC v3) v1))))) ;; let rec EVERY v3 = (fun v4 -> (match v4 with Nil -> true | (Cons (v2, v1)) -> ((v3 v2) && ((EVERY v3) v1)))) ;; let rec EXISTS v3 = (fun v4 -> (match v4 with Nil -> false | (Cons (v2, v1)) -> ((v3 v2) || ((EXISTS v3) v1)))) ;; let rec GENLIST v1 = (fun v2 -> (if (v2 <= 0) then Nil else ((SNOC (v1 (v2 - 1))) ((GENLIST v1) (v2 - 1))))) ;; let PAD_RIGHT = (fun v1 -> (fun v2 -> (fun v3 -> ((APPEND v3) ((GENLIST (K v1)) (let k = (v2 - (LENGTH v3)) in (if (k < 0) then 0 else k))))))) ;; let PAD_LEFT = (fun v1 -> (fun v2 -> (fun v3 -> ((APPEND ((GENLIST (K v1)) (let k = (v2 - (LENGTH v3)) in (if (k < 0) then 0 else k)))) v3)))) ;; let rec MEM v3 = (fun v4 -> (match v4 with Nil -> false | (Cons (v2, v1)) -> ((v3 = v2) || ((MEM v3) v1)))) ;; let rec ALL_DISTINCT v3 = (match v3 with Nil -> true | (Cons (v2, v1)) -> ((((MEM v2) v1) = false) && (ALL_DISTINCT v1))) ;; let rec isPREFIX v5 = (fun v6 -> (match v5 with Nil -> true | (Cons (v4, v3)) -> (match v6 with Nil -> false | (Cons (v2, v1)) -> ((v4 = v2) && ((isPREFIX v3) v1))))) ;; let rec FRONT x1 = (match x1 with Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) | (Cons (v2, v1)) -> (if (v1 = Nil) then Nil else (Cons (v2, (FRONT v1))))) ;; let rec ZIP x1 = (match x1 with (Pair (v8, v7)) -> (match v8 with Nil -> (match v7 with Nil -> Nil | (Cons (v2, v1)) -> (raise (Match_failure (string_of_bool true, 0, 0)))) | (Cons (v6, v5)) -> (match v7 with Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) | (Cons (v4, v3)) -> (Cons ((Pair (v6, v4)), (ZIP (Pair (v5, v3)))))))) ;; let rec EL v1 = (fun v2 -> (if (v1 <= 0) then (HD v2) else ((EL (v1 - 1)) (TL v2)))) ;; let rec PART v3 = (fun v4 -> (fun v5 -> (fun v6 -> (match v4 with Nil -> (Pair (v5, v6)) | (Cons (v2, v1)) -> (if (v3 v2) then ((((PART v3) v1) (Cons (v2, v5))) v6) else ((((PART v3) v1) v5) (Cons (v2, v6)))))))) ;; let PARTITION = (fun v1 -> (fun v2 -> ((((PART v1) v2) Nil) Nil))) ;; let rec QSORT v7 = (fun v8 -> (match v8 with Nil -> Nil | (Cons (v6, v5)) -> (let v3 = ((PARTITION (fun v4 -> ((v7 v4) v6))) v5) in (match v3 with (Pair (v2, v1)) -> ((APPEND ((APPEND ((QSORT v7) v2)) (Cons (v6, Nil)))) ((QSORT v7) v1)))))) ;; let rec EXP_AUX v2 = (fun v3 -> (fun v1 -> (if (v3 <= 0) then v1 else (((EXP_AUX v2) (v3 - 1)) (v2 * v1))))) ;; let EXP = (fun v1 -> (fun v2 -> (((EXP_AUX v1) v2) 1))) ;; let MIN = (fun v1 -> (fun v2 -> (if (v1 < v2) then v1 else v2))) ;; let MAX = (fun v1 -> (fun v2 -> (if (v1 < v2) then v2 else v1))) ;; let EVEN = (fun v1 -> ((v1 mod 2) <= 0)) ;; let ODD = (fun v1 -> (0 < (v1 mod 2))) ;; let rec FUNPOW v1 = (fun v2 -> (fun v3 -> (if (v2 <= 0) then v3 else (((FUNPOW v1) (v2 - 1)) (v1 v3))))) ;; let MOD_2EXP = (fun v2 -> (fun v1 -> (v1 mod ((EXP 2) v2)))) ;; let DIV_2EXP = (fun v2 -> (fun v1 -> (v1 / ((EXP 2) v2)))) ;; let PRE = (fun v1 -> (let k = (v1 - 1) in (if (k < 0) then 0 else k))) ;; let ABS_DIFF = (fun v2 -> (fun v1 -> (if (v2 < v1) then (let k = (v1 - v2) in (if (k < 0) then 0 else k)) else (let k = (v2 - v1) in (if (k < 0) then 0 else k))))) ;; let DIV2 = (fun v1 -> (v1 / 2)) ;; let rec string_lt v7 = (fun v8 -> (match v7 with Nil -> (match v8 with Nil -> false | (Cons (v2, v1)) -> true) | (Cons (v6, v5)) -> (match v8 with Nil -> false | (Cons (v4, v3)) -> (( (let m = v6 in (fun n -> (m < n))) v4) || ((v6 = v4) && ((string_lt v5) v3)))))) ;; let string_le = (fun v1 -> (fun v2 -> ((v1 = v2) || ((string_lt v1) v2)))) ;; let string_gt = (fun v1 -> (fun v2 -> ((string_lt v2) v1))) ;; let string_ge = (fun v1 -> (fun v2 -> ((string_le v2) v1))) ;; let BITS = (fun v1 -> (fun v2 -> (fun v3 -> ((v3 mod ((EXP 2) (v1 + 1))) / ((EXP 2) v2))))) ;; let BIT = (fun v1 -> (fun v2 -> (((v2 / ((EXP 2) v1)) mod 2) = 1))) ;; let SBIT = (fun v1 -> (fun v2 -> (if v1 then ((EXP 2) v2) else 0))) ;; type ('a) ptree = Branch of int * int * ('a) ptree * ('a) ptree | Leaf of int * 'a | Empty ;; let rec BRANCHING_BIT v1 = (fun v2 -> (if (((ODD v1) = (EVEN v2)) || (v1 = v2)) then 0 else (((BRANCHING_BIT (DIV2 v1)) (DIV2 v2)) + 1))) ;; let rec PEEK v7 = (fun v8 -> (match v7 with Empty -> None | (Leaf (v2, v1)) -> (if (v8 = v2) then (Some (v1)) else None) | (Branch (v6, v5, v4, v3)) -> ((PEEK (if ((BIT v5) v8) then v4 else v3)) v8))) ;; let MOD_2EXP_EQ = (fun v3 -> (fun v1 -> (fun v2 -> (((MOD_2EXP v3) v1) = ((MOD_2EXP v3) v2))))) ;; let JOIN = (fun v8 -> (match v8 with (Pair (v7, v6)) -> (match v6 with (Pair (v5, v4)) -> (match v4 with (Pair (v3, v2)) -> (let v1 = ((BRANCHING_BIT v7) v3) in (if ((BIT v1) v7) then (Branch (((MOD_2EXP v1) v7), v1, v5, v2)) else (Branch (((MOD_2EXP v1) v7), v1, v2, v5)))))))) ;; let rec ADD v13 = (fun v14 -> (match v13 with Empty -> (match v14 with (Pair (v2, v1)) -> (Leaf (v2, v1))) | (Leaf (v6, v5)) -> (match v14 with (Pair (v4, v3)) -> (if (v6 = v4) then (Leaf (v4, v3)) else (JOIN (Pair (v4, (Pair ((Leaf (v4, v3)), (Pair (v6, (Leaf (v6, v5))))))))))) | (Branch (v12, v11, v10, v9)) -> (match v14 with (Pair (v8, v7)) -> (if (((MOD_2EXP_EQ v11) v8) v12) then (if ((BIT v11) v8) then (Branch (v12, v11, ((ADD v10) (Pair (v8, v7))), v9)) else (Branch (v12, v11, v10, ((ADD v9) (Pair (v8, v7)))))) else (JOIN (Pair (v8, (Pair ((Leaf (v8, v7)), (Pair (v12, (Branch (v12, v11, v10, v9))))))))))))) ;; let BRANCH = (fun v31 -> (match v31 with (Pair (v30, v29)) -> (match v29 with (Pair (v28, v27)) -> (match v27 with (Pair (v26, v25)) -> (match v26 with Empty -> (match v25 with Empty -> Empty | (Leaf (v2, v1)) -> (Leaf (v2, v1)) | (Branch (v6, v5, v4, v3)) -> (Branch (v6, v5, v4, v3))) | (Leaf (v14, v13)) -> (match v25 with Empty -> (Leaf (v14, v13)) | (Leaf (v8, v7)) -> (Branch (v30, v28, (Leaf (v14, v13)), (Leaf (v8, v7)))) | (Branch (v12, v11, v10, v9)) -> (Branch (v30, v28, (Leaf (v14, v13)), (Branch (v12, v11, v10, v9))))) | (Branch (v24, v23, v22, v21)) -> (match v25 with Empty -> (Branch (v24, v23, v22, v21)) | (Leaf (v16, v15)) -> (Branch (v30, v28, (Branch (v24, v23, v22, v21)), (Leaf (v16, v15)))) | (Branch (v20, v19, v18, v17)) -> (Branch (v30, v28, (Branch (v24, v23, v22, v21)), (Branch (v20, v19, v18, v17)))))))))) ;; let rec REMOVE v7 = (fun v8 -> (match v7 with Empty -> Empty | (Leaf (v2, v1)) -> (if (v2 = v8) then Empty else (Leaf (v2, v1))) | (Branch (v6, v5, v4, v3)) -> (if (((MOD_2EXP_EQ v5) v8) v6) then (if ((BIT v5) v8) then (BRANCH (Pair (v6, (Pair (v5, (Pair (((REMOVE v4) v8), v3))))))) else (BRANCH (Pair (v6, (Pair (v5, (Pair (v4, ((REMOVE v3) v8))))))))) else (Branch (v6, v5, v4, v3))))) ;;