type list = Nil | Node of node
 and node = { key:int; mutable prev : list; mutable next : list };;

let (!^) = function
    Nil -> invalid_arg "invalid"
  | Node n -> n;;

let new_node key = {key=key;prev=Nil;next=Nil};;
let hd = new_node (-1) and
    tl = new_node (-1);;

let () =
  hd.next <- (Node tl);
  ((!^) hd.next).prev <- (Node hd);;

let insert key =
  let c = new_node key in
  c.next <- hd.next;
  ((!^) hd.next).prev <- (Node c);
  hd.next <- (Node c);
  c.prev <- (Node hd)
;;

let print_list () =
  let current_node = ((!^) hd.next) in
  let rec loop node i =
    if node == tl then print_newline ()
    else
      begin
        if i = 1 then print_string " ";
        Printf.printf "%d" (node.key);
        loop ((!^) node.next) 1
      end
  in loop current_node 0
;;

let delete_node node =
  if node == tl then ()
  else
    begin
      ((!^) node.prev).next <- node.next;
      ((!^) node.next).prev <- node.prev
    end
;;

let delete_first () =
  delete_node ((!^) hd.next);;

let delete_last () =
  delete_node ((!^) tl.prev);;

let search_list key =
  let current_node = ((!^) hd.next) in
  let rec loop node =
    if node != tl && node.key != key then
      loop ((!^) node.next)
    else
      node
  in loop current_node
;;

let delete key =
  delete_node (search_list key);;

let split str =
  let rec split_inner ct b=
    if String.length str == ct then [b]
    else
      match str.[ct] with
        ' ' -> b::split_inner (ct+1) ""
      | c -> split_inner (ct+1) (b^(Char.escaped c))
  in split_inner 0 "";;

let () =
  let n = read_int () in
  let rec read = function
      0 -> print_list ()
    | i ->
       let line = read_line ()
                |> split
                |> Array.of_list
       in
       let op = line.(0) in
       if op = "insert" then
         insert (int_of_string line.(1))
       else if op = "delete" then
         delete (int_of_string line.(1))
       else if op = "deleteFirst" then
         delete_first ()
       else if op = "deleteLast" then
         delete_last ()
       ;read (i-1)
  in read n;;