let rec length list =
  match list with
      []  -> 0
    |e::l -> 1 + length l ;;

let rec append  x y = if y = []
  then
    x
  else
    let rec appendlist  = function
    [] -> y
 |e::l -> e::appendlist l
    in appendlist x ;;

let rec couplesize list = match list with
    []       -> 0
  |(x,y)::l  -> x + couplesize l ;;

let nth n list =
  if n < 0 then
     invalid_arg "nth: index  must be a natural"
  else
     let rec nth_rec = function
           (_, []) -> failwith "nth: list is too  short"
         | (1, e::l) -> e
         | (i, e::l) -> nth_rec (i-1, l)
      in
     nth_rec (n+1, list) ;;

let search_pos n list  =
    let rec searchp n list i = match list with
      [] -> failwith "shorsearch_pos: not  found"
      | e ::l when n=e -> i
      | _ :: l  -> searchp n l i+1
    in
    searchp n list 0 ;;

let rec sum_digits n = match n with
   n when n=0 -> 0
  | _ -> n mod 10 +  sum_digits (n/10) ;;

let rec common (list1,list2) = match (list1,list2) with
  | ([],_) -> 0
  | (_,[]) -> 0
  |((e1::l1),(e2::l2)) when e1=e2 -> e1
  |((e1::l1),(e2::l2)) when e1 < e2 ->  common (e2::l2,e1::l1)
  |((list1,_::l2)) -> common (l2,list1) ;;


let rec prefix (list1,list2) = match (list1,list2) with
    ([],_) -> true
  | (_,[]) -> true
  | (e1::l1,e2::l2) when e1=e2 -> prefix (l1,l2)
  | (e1::l1,e2::l2) -> false;;

let init_list n x = if n < 0
  then
    invalid_arg "init_list: n must be a natural"
  else
    let rec init n x = match n with
       0 -> []
      |_ -> x:: init (n-1) x
    in
    init n x ;;

let rec put_list n x list = match (x,list) with
    (_,[]) -> list
  | (0,e::l) -> n::l
  | (i,e::l) -> e:: put_list n (x-1) l ;;


let rec length list =
  match list with
      []  -> 0
    |e::l -> 1 + length l ;;

let rec append  x y = if y = []
  then
    x
  else
    let rec appendlist  = function
    [] -> y
 |e::l -> e::appendlist l
    in appendlist x ;;

let rec couplesize list = match list with
    []       -> 0
  |(x,y)::l  -> x + couplesize l ;;

let nth n list =
  if n < 0 then
     invalid_arg "nth: index  must be a natural"
  else
     let rec nth_rec = function
           (_, []) -> failwith "nth: list is too  short"
         | (1, e::l) -> e
         | (i, e::l) -> nth_rec (i-1, l)
      in
     nth_rec (n+1, list) ;;

let search_pos n list  =
    let rec searchp n list i = match list with
      [] -> failwith "shorsearch_pos: not  found"
      | e ::l when n=e -> i
      | _ :: l  -> searchp n l i+1
    in
    searchp n list 0 ;;

let rec sum_digits n = match n with
   n when n=0 -> 0
  | _ -> n mod 10 +  sum_digits (n/10) ;;

let rec common (list1,list2) = match (list1,list2) with
  | ([],_) -> 0
  | (_,[]) -> 0
  |((e1::l1),(e2::l2)) when e1=e2 -> e1
  |((e1::l1),(e2::l2)) when e1 < e2 ->  common (e2::l2,e1::l1)
  |((list1,_::l2)) -> common (l2,list1) ;;


let rec prefix (list1,list2) = match (list1,list2) with
    ([],_) -> true
  | (_,[]) -> true
  | (e1::l1,e2::l2) when e1=e2 -> prefix (l1,l2)
  | (e1::l1,e2::l2) -> false

let init_list n x = if n < 0
  then
    invalid_arg "init_list: n must be a natural"
  else
    let rec init n x = match n with
       0 -> []
      |_ -> x:: init (n-1) x
    in
    init n x ;;

let rec put_list n x list = match (x,list) with
    (_,[]) -> list
  | (0,e::l) -> n::l
  | (i,e::l) -> e:: put_list n (x-1) l ;;

let init_board (l,c) v =  init_list l (init_list c v);;

let get_cell (x,y) board = nth y (nth x (board));;


let init_board (l,c) v =  init_list l (init_list c v);;

let get_cell (x,y) board = nth y (nth x (board));;


let put_cell v (x,y) b =
  put_list (put_list v y (nth x b)) x b ;;