type direction = N | E | W | S

type state = { dir : direction; pos : int * int }

let vert (x, y) = y * 5 + x

let has_edge grid ((x1, y1) as p1) ((x2, y2) as p2) =
  let v1, v2 = (vert p1), (vert p2) in
  try grid.(v1).(v2) with Invalid_argument _ -> false

let set_edge grid ((x1, y1) as p1) ((x2, y2) as p2) =
  let v1, v2 = (vert p1), (vert p2) in
  grid.(v1).(v2) <- true;
  grid.(v2).(v1) <- true

let load_grid grid =
  let rec loop i =
    let line = read_line () in
    for j = 0 to (String.length line) - 1 do
      if line.[j] = '1' then
        set_edge grid
                 (j, i / 2)
                 (if i mod 2 = 0 then (j + 1, i / 2) else (j, i / 2 + 1))
    done;
    loop (succ i)
  in
  try loop 0 with End_of_file -> ()

let rec forward grid { dir = d; pos = (x, y) as p } =
  let has_edge_to = has_edge grid (x, y) in
  match d with
  | N -> if has_edge_to (x - 1, y) then
           { dir = W; pos = (x - 1, y) }
         else if has_edge_to (x, y - 1) then
           { dir = d; pos = (x, y - 1) }
         else
           forward grid { dir = E; pos = p }
  | E -> if has_edge_to (x, y - 1) then
           { dir = N; pos = (x, y - 1) }
         else if has_edge_to (x + 1, y) then
           { dir = d; pos = (x + 1, y) }
         else
           forward grid { dir = S; pos = p }
  | S -> if has_edge_to (x + 1, y) then
           { dir = E; pos = (x + 1, y) }
         else if has_edge_to (x, y + 1) then
            { dir = d; pos = (x, y + 1) }
         else
           forward grid { dir = W; pos = p }
  | W -> if has_edge_to (x, y + 1) then
           { dir = S; pos = (x, y + 1) }
         else if has_edge_to (x - 1, y) then
           { dir = d; pos = (x - 1, y) }
         else
           forward grid { dir = N; pos = p }

let () =
  let grid = Array.init 25 (fun _ -> Array.make 25 false) in
  load_grid grid;
  let rec loop s =
    let s = forward grid s in
    print_char
      begin
        match s.dir with
        | N -> 'U'
        | E -> 'R'
        | S -> 'D'
        | W -> 'L'
      end;
    if s.pos = (0, 0) then print_newline ()
    else loop s
  in
  loop { dir = E; pos = (0, 0) }