type trie = Node of trie * trie | Allow | Deny | None;;

let rec put_rule trie rule allow =
  match (trie, rule) with
    (Allow, _) | (Deny, _) -> trie
  | (None, []) -> if allow then Allow else Deny
  | (None, 0::rule') -> Node (put_rule None rule' allow, None)
  | (None, 1::rule') -> Node (None, put_rule None rule' allow)
  | (Node (zero,one), 0::rule') -> Node (put_rule zero rule' allow, one)
  | (Node (zero,one), 1::rule') -> Node (zero, put_rule one rule' allow)
  | (Node (zero,one), []) -> Node (put_rule zero [] allow, put_rule one [] allow)
  | (_, _::_) -> failwith "Impossible combination";;

let rec print_trie trie a =
  match trie with 
    Allow -> print_string (a^" - allow\n")
  | Deny -> print_string (a^" - deny\n")
  | None -> print_string (a^" - none\n")
  | Node (z,o) -> print_trie z (a^"0"); print_trie o (a^"1");;

let rec check trie address =
  match (trie, address) with
    (Allow, _) -> true
  | (Deny, _) -> false
  | (None, _) -> true
  | (Node (zero,_), 0::address') -> check zero address'
  | (Node (_,one), 1::address') -> check one address'
  | (_, []) -> failwith "Address is too short?"
  | (_, _::_) -> failwith "Incorrect number in address";;

let (inp,out) = (Scanf.Scanning.from_file "access.in", open_out "access.out");;

let rec trim len list n = 
  match list with
    l1::ls when len > n -> l1::trim (len-1) ls n 
  | _ -> [];;

let rec to_bin n v = if n >= 0 then ((v lsr n) mod 2) :: to_bin (n-1) v else [];;
let conv list = List.flatten (List.map (to_bin 7) list);;

let parse_address () =
  let addr = Scanf.bscanf inp " %d.%d.%d.%d" (fun a b c d -> (conv [a;b;c;d])) in
  try Scanf.bscanf inp "/%d" (trim 32 addr)
  with Scanf.Scan_failure _ -> addr;;

let trie = ref None;;

let rules = Scanf.bscanf inp " %d " (fun n -> n);;
for i = 1 to rules do
  let allow = Scanf.bscanf inp " %s from " (fun x -> x = "allow") in
  let address = parse_address () in
  trie := put_rule !trie address allow
done;;

(*print_trie !trie "";;*)

let addrs = Scanf.bscanf inp " %d " (fun n -> n);;
for i = 1 to addrs do
  Printf.fprintf out "%c" (if check !trie (parse_address ()) then 'A' else 'D')
done;;

close_out out;;
