(in-package #:cl-user)

;;;
;;; Init
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  ;; #+swank (declaim (optimize (speed 3) (safety 2)))
  #+swank (declaim (optimize (speed 0) (safety 3) (debug 3)))
  #-swank (declaim (optimize (speed 3) (safety 0) (debug 0)))
  #-swank (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))
  #-swank (sb-ext:disable-debugger))

;;;
;;; Reader Macros
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (set-dispatch-macro-character
   #\# #\f
   #'(lambda (stream c2 n)
       (declare (ignore c2 n))
       (let ((form (read stream t nil t)))
         `(lambda (&optional %) (declare (ignorable %)) ,form))))

  (set-dispatch-macro-character
   #\# #\>
   #'(lambda (stream c2 n)
       (declare (ignore c2 n))
       (let ((form (read stream t nil t)))
         (declare (ignorable form))
         #-swank nil
         #+swank (if (atom form)
                     `(format *error-output* "~a => ~a~&" ',form ,form)
                     `(format *error-output* "~a => ~a~&" ',form `(,,@form)))))))

;;;
;;; Libraries
;;;

;;;
;;; BOF
;;;

(defpackage randomized-heap
  (:use #:cl)
  (:nicknames #:rh)
  (:shadow #:count)
  (:export #:make-randomized-heap
           #:empty-p
           #:push!
           #:pop!
           #:peak
           #:count
           #:do-all-kvs
           #:prune!))

(in-package #:randomized-heap)

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defvar *OPT*
    #+swank '(optimize (speed 3) (safety 2) (debug 3))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))))

(declaim (inline %make-node make-randomized-heap))
(defstruct (node (:constructor %make-node)
                 (:conc-name %n-))
  (key nil :type fixnum)
  (value nil :type t)
  (children (make-array 2 :element-type '(or null node)
                          :initial-element nil)
   :type (simple-array (or null node) (2))))

(defstruct (randomized-heap (:constructor make-randomized-heap (&optional (compare #'sb-impl::two-arg-<) (key-fn #'identity))))
  (root nil :type (or null node))
  (count 0 :type (integer 0 #.most-positive-fixnum))
  (comparator compare :type (function (fixnum fixnum) boolean))
  (key-fn key-fn :type (function (t) fixnum)))

(defun count (heap)
  (randomized-heap-count heap))

(declaim (inline %direction))
(defun %direction ()
  (declare #.*OPT*)
  (random 2))

(defun meld (l r comparator)
  (declare #.*OPT*
           ((or null node) l r)
           ((function (fixnum fixnum) boolean) comparator))
  (cond
    ((or (null l)
         (null r))
     (or l r))
    ((funcall comparator
              (%n-key l)
              (%n-key r))
     ;; l is root
     (let ((dir (%direction)))
       (setf (aref (%n-children l) dir)
             (meld (aref (%n-children l) dir)
                   r
                   comparator))
       l))
    (t
     ;; r is root
     (let ((dir (%direction)))
       (setf (aref (%n-children r) dir)
             (meld l
                   (aref (%n-children r) dir)
                   comparator))
       r))))

(declaim (inline peak))
(defun peak (heap)
  (declare #.*OPT*)
  (let ((root (randomized-heap-root heap)))
    (values (%n-value root)
            (%n-key root))))

(defun empty-p (heap)
  (null (randomized-heap-root heap)))

(declaim (inline pop! push!))
(defun pop! (heap)
  (declare #.*OPT*)
  (when (empty-p heap)
    (error "heap is empty"))
  (decf (randomized-heap-count heap))
  (multiple-value-bind (value key)
      (peak heap)
    (let* ((children (%n-children (randomized-heap-root heap)))
           (l (aref children 0))
           (r (aref children 1)))
      (setf (randomized-heap-root heap)
            (meld l
                  r
                  (randomized-heap-comparator heap)))
      (values value key))))

(defun push! (heap value)
  (declare #.*OPT*)
  (let ((key (funcall (randomized-heap-key-fn heap)
                      value)))
    (incf (randomized-heap-count heap))
    (setf (randomized-heap-root heap)
          (meld (randomized-heap-root heap)
                (%make-node :key key
                            :value value)
                (randomized-heap-comparator heap))))
  heap)

(defmacro do-all-kvs ((key value heap) &body body &environment env)
  (let ((temp (gensym)))
    (multiple-value-bind (args argvs res setter accessor)
        (get-setf-expansion heap env)
      `(let ((,temp (make-randomized-heap (randomized-heap-comparator ,accessor)
                                          (randomized-heap-key-fn ,accessor))))
         (loop :until (empty-p ,accessor)
               :do (multiple-value-bind (,value ,key)
                       (pop! ,accessor)
                     (progn ,@body)
                     (push! ,temp ,value)))
         (let* (,@(mapcar #'list args argvs)
                (,(car res) ,temp))
           ,setter
           nil)))))

(defun prune! (heap cnt)
  (let ((new-root nil)
        (comparator (randomized-heap-comparator heap)))
    (dotimes (_ cnt)
      (multiple-value-bind (v k) (pop! heap)
        (setf new-root
              (meld new-root
                    (%make-node :key k :value v)
                    comparator))))
    (setf (randomized-heap-root heap)
          new-root)))

;;;
;;; EOF
;;;

;;;
;;; Solution
;;;

(defpackage macro
  (:use #:cl)
  (:nicknames #:m)
  (:export #:while
           #:eval-always))

(in-package macro)

(defmacro while (test &body body)
  `(loop while ,test do (progn ,@body)))

(defmacro eval-always (&body body)
  `(eval-when (:compile-toplevel :load-toplevel :execute)
     ,@body))


(defpackage util
  (:use #:cl)
  (:nicknames #:u)
  (:export #:manhattan-dist
           #:+dir-dy-dx+
           #:+dy-dx+
           #:+dirs+
           #:coords->dir))

(in-package util)

(defun manhattan-dist (c1 c2)
  (+ (abs (- (car c1) (car c2)))
     (abs (- (cdr c1) (cdr c2)))))

(sb-int:defconstant-eqx +dir-dy-dx+
    '((#\U . (-1 . 0))
      (#\D . (1 . 0))
      (#\L . (0 . -1))
      (#\R . (0 . 1)))
  #'equalp)

(sb-int:defconstant-eqx +dy-dx+ (map 'list #'cdr +dir-dy-dx+) #'equal)
(sb-int:defconstant-eqx +dirs+ (map 'list #'car +dir-dy-dx+) #'equal)

(defun coords->dir (c1 c2)
  (destructuring-bind (y1 . x1) c1
    (destructuring-bind (y2 . x2) c2
      (let ((dy (signum (- y2 y1)))
            (dx (signum (- x2 x1))))
        (car (rassoc (cons dy dx) +dir-dy-dx+ :test #'equal))))))

#+swank
(progn
  (assert (eql #\R (coords->dir '(0 . 0) '(0 . 1))))
  (assert (eql #\D (coords->dir '(0 . 0) '(1 . 0))))
  (assert (eql #\U (coords->dir '(0 . 0) '(-1 . 0))))
  (assert (eql #\L (coords->dir '(0 . 0) '(0 . -1)))))


(in-package cl-user)

(defconstant +grid-size+ 60)
(defconstant +vital+ 1500)

(defstruct trap
  (id nil :type fixnum)
  (coord nil :type cons)
  (power nil :type fixnum)
  (interval nil :type fixnum))

;; jewel/start/goal/key をcheckpointと呼ぶことにする

(defstruct checkpoint
  (id nil :type fixnum)
  (coord nil :type cons)
  (type nil :type (member :jewel :start :goal :key)))

(defun get-trap-factor (grid traps)
  (let ((factors (make-array (list +grid-size+ +grid-size+) :element-type 'single-float
                                                            :initial-element 0.0)))
    (sb-int:dovector (trap traps)
      (destructuring-bind (sy . sx) (trap-coord trap)
        (loop for (dy . dx) in u:+dy-dx+
              do (loop with y = (+ sy dy)
                       with x = (+ sx dx)
                       while (and (<= 0 y (1- +grid-size+))
                                  (<= 0 x (1- +grid-size+))
                                  (not (find (aref grid y x)
                                             "#E")))
                       do (incf (aref factors y x) (/ (trap-power trap)
                                                      (trap-interval trap)))
                       do (incf y dy)
                          (incf x dx)))
        (incf (aref factors sy sx) (/ (trap-power trap)
                                      (trap-interval trap)))))
    factors))

(defun get-real-trap-factor (grid traps)
  (let ((factors (make-array (list +grid-size+ +grid-size+ 60) :element-type 'fixnum
                                                               :initial-element 0)))
    (sb-int:dovector (trap traps)
      (destructuring-bind (sy . sx) (trap-coord trap)
        (loop for (dy . dx) in u:+dy-dx+
              do (loop with y = (+ sy dy)
                       with x = (+ sx dx)
                       while (and (<= 0 y (1- +grid-size+))
                                  (<= 0 x (1- +grid-size+))
                                  (not (find (aref grid y x)
                                             "#E")))
                       do (loop for dd below 60 by (trap-interval trap)
                                do (incf (aref factors y x dd) (trap-power trap)))
                       do (incf y dy)
                          (incf x dx)))
        (loop for dd below 60 by (trap-interval trap)
              do (incf (aref factors sy sx dd) (trap-power trap)))))
    factors))

(defstruct (edge-between-checkpoints (:conc-name edge-))
  (dist-id nil :type fixnum)
  (estimated-cost nil :type single-float)
  (dirs nil :type list))

(defconstant +cost-threshold-between-checkpoints+ 100)

(defun get-estimated-cost-edges-between-checkpoints (grid checkpoints trap-factors)
  (let* ((n (length checkpoints))
         (coord-by-id (make-array n))
         (id-by-coord (make-hash-table :test #'equal))
         (edges-by-id (make-array n :initial-element nil)))
    (dolist (cp (coerce checkpoints 'list))
      (setf (gethash (checkpoint-coord cp) id-by-coord) (checkpoint-id cp)
            (aref coord-by-id (checkpoint-id cp)) (checkpoint-coord cp)))
    ;; 距離100以下でたどり着けるものと辺でつなぐ
    (sb-int:dovector (cp checkpoints)
      (destructuring-bind (sy . sx) (checkpoint-coord cp)
        (let (;; (cost y x path)
              (min-heap (rh:make-randomized-heap #'< #'first))
              (cost-by-coord (make-hash-table :test #'equal)))
          (rh:push! min-heap (list 0.0 sy sx nil))
          (m:while (not (rh:empty-p min-heap))
            (destructuring-bind (cost y x path) (rh:pop! min-heap)
              (when (<= cost #1=(gethash (cons y x) cost-by-coord (1+ +cost-threshold-between-checkpoints+)))
                (setf #1# cost)
                (let ((id (gethash (cons y x) id-by-coord)))
                  (when id
                    (push (make-edge-between-checkpoints :dist-id id
                                                         :estimated-cost cost
                                                         :dirs (reverse path))
                          (aref edges-by-id (checkpoint-id cp)))))
                (loop for (dy . dx) in u:+dy-dx+
                      for ny = (+ y dy)
                      for nx = (+ x dx)
                      when (and (<= 0 ny (1- +grid-size+))
                                (<= 0 nx (1- +grid-size+))
                                (not (find (aref grid ny nx)
                                           "#E"))
                                (< (+ cost
                                      (aref trap-factors ny nx)
                                      1)
                                   #2=(gethash (cons ny nx) cost-by-coord (1+ +cost-threshold-between-checkpoints+))))
                        do (setf #2# (+ cost (aref trap-factors ny nx) 1))
                        and do (rh:push! min-heap (list #2#
                                                        ny
                                                        nx
                                                        (cons (u:coords->dir (cons y x)
                                                                             (cons ny nx))
                                                              path))))))))))
    edges-by-id))

(defun get-estimated-costs-and-dirs-between-checkpoints (checkpoints edges-by-id)
  (let* ((n (length checkpoints))
         (costs-and-dirs (make-array (list n n) :initial-element (cons #.(expt 10 12) nil))))
    (dotimes (i n)
      (let (;; (cost id path)
            (min-heap (rh:make-randomized-heap #'< #'first)))
        (rh:push! min-heap (list 0.0 i nil))
        (m:while (not (rh:empty-p min-heap))
          (destructuring-bind (cost j path) (rh:pop! min-heap)
            (when (<= cost (car (aref costs-and-dirs i j)))
              (setf (aref costs-and-dirs i j)
                    (cons cost path))
              (dolist (edge (aref edges-by-id j))
                (let* ((k (edge-dist-id edge))
                       (nc (+ cost
                              (edge-estimated-cost edge)))
                       (npath (cons (edge-dirs edge) path)))
                  (when (< nc (car (aref costs-and-dirs i k)))
                    (setf (aref costs-and-dirs i k)
                          (cons nc npath))
                    (rh:push! min-heap (list nc k npath))))))))))
    (dotimes (i n)
      (dotimes (j n)
        (destructuring-bind (cost . dirs) (aref costs-and-dirs i j)
          (setf (aref costs-and-dirs i j)
                (cons cost (apply #'append (reverse dirs)))))))
    costs-and-dirs))

(defun find-chars (sm c)
  (destructuring-bind (h w) (array-dimensions sm)
    (let ((res nil))
      (dotimes (y h)
        (dotimes (x w)
          (when (eql (aref sm y x)
                     c)
            (push (cons y x)
                  res))))
      (reverse res))))

(defun orders->dirs (orders costs-and-dirs)
  (let ((res nil))
    (dotimes (i (1- (length orders)))
      (let* ((cp1 (aref orders i))
             (cp2 (aref orders (1+ i)))
             (dirs (cdr (aref costs-and-dirs (checkpoint-id cp1) (checkpoint-id cp2)))))
        ;; #> ((car (aref costs-and-dirs (checkpoint-id cp1) (checkpoint-id cp2))))
        (push dirs res)))
    (apply #'append (reverse res))))

(defun validate-dirs (grid dirs)
  (let* ((pos (first (find-chars grid #\S)))
         (key (first (find-chars grid #\K)))
         (y (car pos))
         (x (cdr pos))
         (key-visited nil))
    (dolist (dir dirs)
      (destructuring-bind (dy . dx) (cdr (assoc dir u:+dir-dy-dx+))
        (setf y (+ y dy))
        (setf x (+ x dx))
        (unless (and (<= 0 y (1- +grid-size+))
                     (<= 0 x (1- +grid-size+)))
          (error "out of grid"))
        (when (find (aref grid y x) "#E")
          (error "on trap or wall"))
        (when (equal (cons y x) key)
          (setf key-visited t))))
    (unless key-visited
      (error "key not unreached"))
    (unless (equal (cons y x)
                   (first (find-chars grid #\G)))
      (error "goal is ~a, but ended at ~a" (first (find-chars grid #\G)) (cons y x)))))

(defun get-insts (grid dirs traps)
  "ゴールできない場合はnilを返す"
  ;; TODO waitを使う
  (let* ((pos (first (find-chars grid #\S)))
         (key (first (find-chars grid #\K)))
         (y (car pos))
         (x (cdr pos))
         (factors (get-real-trap-factor grid traps))
         (res nil)
         (rest-vital +vital+)
         (key-visited nil)
         (turn 1))
    (dolist (dir dirs)
      (destructuring-bind (dy . dx) (cdr (assoc dir u:+dir-dy-dx+))
        (setf y (+ y dy))
        (setf x (+ x dx))
        (push (cons :move dir) res)
        (unless (and (<= 0 y (1- +grid-size+))
                     (<= 0 x (1- +grid-size+)))
          (error "out of grid"))
        (when (find (aref grid y x) "#E")
          (error "on trap or wall"))
        (when (equal (cons y x) key)
          (setf key-visited t))
        (decf rest-vital (1+ (aref factors y x (rem turn 60))))
        (when (<= rest-vital 0)
          (return-from get-insts nil))
        (incf turn)))
    #>rest-vital
    (unless key-visited
      (error "key not unreached"))
    (unless (equal (cons y x)
                   (first (find-chars grid #\G)))
      (error "goal is ~a, but ended at ~a" (first (find-chars grid #\G)) (cons y x)))
    (reverse res)))

(defun main ()
  (let* ((n (read))
         (d (read))
         (h (read))
         (grid (make-array (list n n) :element-type 'base-char
                                      :initial-element #\Nul))
         (checkpoints (make-array 0 :fill-pointer 0))
         (traps (make-array 0 :fill-pointer 0)))
    (dotimes (y n)
      (let ((tmp (read-line)))
        (dotimes (x n)
          (setf (aref grid y x) (char tmp x))
          (ecase (char tmp x)
            ((#\S #\K #\G #\J)
             (vector-push-extend (make-checkpoint :id (fill-pointer checkpoints)
                                                  :coord (cons y x)
                                                  :type (ecase (char tmp x)
                                                          (#\S :start)
                                                          (#\K :key)
                                                          (#\G :goal)
                                                          (#\J :jewel)))
                                 checkpoints))
            ;; 残りは一旦無視
            ((#\T #\E #\. #\F #\#)
             nil)))))
    (dotimes (_ (read))
      (vector-push-extend
       (make-trap :id (fill-pointer traps)
                  :coord (cons (read) (read))
                  :power d
                  :interval (read))
       traps))
    (let* ((trap-factors (get-trap-factor grid traps))
           (edges-by-cp-id (get-estimated-cost-edges-between-checkpoints grid checkpoints trap-factors))
           (costs-and-dirs (get-estimated-costs-and-dirs-between-checkpoints checkpoints edges-by-cp-id))
           (find-checkpoint (lambda (type)
                              (find-if (lambda (cp)
                                         (eq (checkpoint-type cp) type))
                                       checkpoints)))
           (start (funcall find-checkpoint :start))
           (goal (funcall find-checkpoint :goal))
           (key (funcall find-checkpoint :key))
           (m (fill-pointer checkpoints))
           (fixed (list start key goal)))
      ;; shuffle checkpoints with fisher-yates
      (loop for i downfrom (1- m) to 1
            for j = (random (1+ i))
            do (rotatef (aref checkpoints i)
                        (aref checkpoints j)))
      (loop repeat 20 for available-vital downfrom h by 20 do
        (let* ((orders (vector start key goal))
               (cost (loop for i below (1- (length orders))
                           for cp1 = (aref orders i)
                           for cp2 = (aref orders (1+ i))
                           sum (car (aref costs-and-dirs
                                          (checkpoint-id cp1)
                                          (checkpoint-id cp2))))))
          (when (<= cost available-vital)
            (sb-int:dovector (cp checkpoints)
              (unless (find cp fixed :test #'eq)
                (let ((orders-len (length orders))
                      (insert-index -1)
                      (min-cost-diff #.(expt 10 12)))
                  (loop for i from 1 below orders-len
                        for c1 = (car (aref costs-and-dirs
                                            (checkpoint-id (aref orders (1- i)))
                                            (checkpoint-id cp)))
                        for c2 = (car (aref costs-and-dirs
                                            (checkpoint-id cp)
                                            (checkpoint-id (aref orders i))))
                        for c3 = (car (aref costs-and-dirs
                                            (checkpoint-id (aref orders (1- i)))
                                            (checkpoint-id (aref orders i))))
                        for cost-diff = (+ c1 c2 (- c3))
                        when (< cost-diff min-cost-diff)
                          do (setf min-cost-diff cost-diff
                                   insert-index i))
                  (when (and (>= insert-index 1)
                             (<= (+ cost min-cost-diff) available-vital))
                    (setf orders (concatenate 'vector
                                              (subseq orders 0 insert-index)
                                              (vector cp)
                                              (subseq orders insert-index)))
                    (incf cost min-cost-diff)))))
            (assert (eq (aref orders 0) start))
            (assert (eq (aref orders (1- (length orders)))
                        goal))
            (let* ((dirs (orders->dirs orders costs-and-dirs))
                   (insts (get-insts grid dirs traps)))
              (when insts
                #> (available-vital (length orders))
                (dolist (inst insts)
                  (ecase (car inst)
                    (:move
                     (format t "M ~a~%" (cdr inst)))))
                (return-from main))))))
      (error "Not found..."))))

#-swank (main)

;;;
;;; Debug
;;;

#+swank
(defun run ()
  (let ((*standard-input*
          (make-string-input-stream
           (with-output-to-string (*standard-output*)
             (run-program
              (truename "~/.roswell/bin/copy-or-paste")
              '()
              :output *standard-output*)))))
    (main)))

;; Raise error on warning at compile time

#+(and sbcl (not swank))
(eval-when (:compile-toplevel)
  (when (or (plusp sb-c::*compiler-warning-count*)
            sb-c::*undefined-warnings*)
    (error "compiler-error-count:~a, undefined warnings:~a"
           sb-c::*compiler-warning-count*
           sb-c::*undefined-warnings*)))

#+swank
(defun run-sample (infile outfile &optional (out *standard-output*))
  (with-open-file (*standard-input* infile :direction :input)
    (with-open-file (*standard-output* outfile :direction :output
                                               :if-exists :supersede)
      (main))
    (sb-ext:run-program "/usr/bin/java" (list "Judge" infile outfile)
                        :output out
                        :error *error-output*)))

#+swank (declaim (notinline run-sample-zero))
#+swank
(defun run-sample-zero ()
  (gc :full t)
  (with-input-from-string (*standard-input* "60 3 1500
.......JJ....J#..#E#....EE.J..E...E#J.....#.#EE......#..J.J#
#E#.....##J..JE....E..#....J.........#......#..#J.........#.
.J.J.#.#....J.#..#........J#...#J#.KJE.J.E.#J.#....#......J.
J..E..#.E#.......E........JEJ.....F..##..............#...J.J
..J.......JE...#......J.#.#..#J#JFJ.......E..#..#....E.....J
#..J.....EE....J........E............##.E#.E.#JJ..........E.
...#......J.J..J#...#...#.#..JE#....##E...#F.#....E....#E#..
.JJ.....###.J.EE...J...#E#E#...E.E.....#E......J..#...#....#
E.E.......#JF.J.J.E.##E#...EE..J....F..#.#J#..E#J..E..J...#F
##....F.#F#.E.#.EJ...J#E..#..#.J.......E...J....#..#..#....S
.E...E...J..J#........#...E.E.......#.....J..J.....E..E....#
.................#J#.....F...JE.#......##.........JJ.J....#.
E..J...E##..#.J...#...#.E....##...#.....EEJJJ.##.#.E.....E#.
E#.F.#.......JF..#..E#......EJ.....#.#.E.##..JJ.......E.J..E
JE..#E....E..E.J#.E...E...J...#J#J.#.E.....E..#E#.E..EF###..
E....J.#..J#....#..EE#.E...E.J.J...E#E#.J..J...E..........J#
.....#..J.#JF.#....E..#EE..E..#.......E.........#..J..#..J.F
#.EF.......E.J.E............#.........#...........E...#.#J..
F.....JJ...E#..E.#....#.E#...#...F.J.#.E.F.#.....J.....#EJ.E
###......#.E.J.E...#E..#..E...#.....#..#.#......F#.E.J..#.#E
....JEEE..EE.#.E#..#JJ............#J.E.#E..J........E....#.E
..E....EJ...J........#..J..J.#E#.#...#.E....#E.#E.#.#E..#..#
...#E#.E.....#J.E.#.#.J.J...E.JJ#J...#.J...##....J.J.......#
.....F....#..J#J..#....#.E...EJ#..#...#.#F#F.EE#..#.....#E.E
J#..#....#.#E..#.J.#.#......EJ..J.............#...#....#.E..
..##EEEE.....JJ..J.#..#..#.E....#J#E#E...E......#JJ#.E..E.#J
#E..##..JJ.#.JE.....E.##.E....E#.....#E.#J..#....JJ..#.#....
.E.#.E....#E..E..JEJ..JE..#F#..#.#.#..E#J#......#.E.EJ#..F.E
.J....#....J.JE.J#...JF.E..JE.J..#....F.F#..E.##JJE....#F.EE
..F.EJF...E...EE#..J.#F.F#....JE#J.......E#F.....E.....J...#
#E##EJ#.E....E......JJ..F##J..E...J..JE..J.EJ..E.....E.EE.#E
E#...E...JE.#.#..E..#.J....E..#.#.J#.E.E.#.#E.##.#...#...E.J
...G##..EF.J#J.J....E.F.......E#.J...#..E...##........#.E.#.
.....J.#..J...E..EJ..E......J....E...#.#.F#E.EE..#J.E......E
........E.E..#FJ.E#.F..E#.#...........F....J..#.##.##..EFJ.E
....E.#....##.JE...EE.E.#E#..JJEF....#J.#....J.JE..J.....J..
#E...........JJ....###....J#................J..#J.JJ#JE.EJ..
JE.#EJE..#..E..J..#.J.#.....J.J.....#EJJ.E#.E..#E.......E..#
#.#J......#....#...#....J.J.E#J.E##.J....EE.#..E..##J..E....
E..E.F.#E....E.....J.#.#.EJ.#.#.J.#...JJ##..#J.....#J.EJ....
.#J.E#......#..E..#..#...J#J....#.E.J......#F.#.E.EJ..E...#.
....J.E..#.#......J...#.JE.#.E...#..E..E.J.E..#.E...#....#EJ
...##.J..J.J...JEJEJ...#.##.#.EE.F...F#.......E.E...#.....J.
...#F..JJ....J##.......F...#..#E....#JJJE.E.J##.E..J...F#J#.
#....J..#......EJ.#....EE.#...E....E...#.E.J.E...JEE.E..J..#
...#...#.#....#...E.#.E..E.E..F.E.FEE...............F..#.E#.
E.JJ.....E#EJE#....##....#.#.F..#J..#E...#...E.#..##EJ#.#...
F....#....#..........E.E.FE.#E......#..#EE..#...#EE....FE..#
..JJ#J..EE...J........J#.E..E..J..E.#...##......J..J........
..##...#...JJF#J....F....#.....#E.......EJ.........J.#......
....J.#J.....J....##J..#..JJ.#..#.#.#...J.JE##E.JJ....E#.#.E
...#......EE.....JE..........J.J..J#...#.#..#F..#..J..E...#.
E...E..E.F.E#....J....E.#.E.JJ..J.J.J.#.##.....J.E..J.......
##E.....E#EJJ.##.......E.##....EE......E...FE.#.....E.J##..J
..#E#J#......J#......#.#.J....E.#..E..#E.##.#.###......#....
#E#.#J...E.#.JE.#.J...#.....#....J..EE.##EE#..##.......##E..
#.#......#.J.J...E#.E...JE#......#..J.....J#JF..#E.EJ.J.....
J....#...JJ...E......#E.J..##.....#.J.#..#E.E..#.....##..J..
E#E.......J#.....EE.J..##...F.....J.FJ#.E........E........#.
J.E....J.E.J...E.#..E........##..E....#J..#.#..J...#...E#E..
374
0 18 5
0 24 5
0 25 2
0 30 3
0 34 2
0 45 3
0 46 4
1 1 3
1 14 5
1 19 2
2 37 5
2 41 5
3 3 3
3 8 4
3 17 3
3 27 3
4 11 2
4 42 4
4 53 2
5 9 4
5 10 2
5 24 3
5 40 5
5 43 2
5 58 5
6 30 2
6 38 5
6 50 5
6 56 5
7 14 2
7 15 5
7 24 5
7 26 4
7 31 5
7 33 4
7 40 3
8 0 5
8 2 5
8 18 5
8 22 3
8 27 3
8 28 5
8 46 2
8 51 5
9 12 3
9 16 3
9 23 5
9 39 4
10 1 5
10 5 2
10 26 5
10 28 3
10 51 4
10 54 3
11 30 2
12 0 4
12 7 4
12 24 4
12 40 5
12 41 4
12 51 5
12 57 4
13 0 4
13 20 2
13 28 2
13 39 4
13 54 2
13 59 5
14 1 5
14 5 4
14 10 4
14 13 5
14 18 2
14 22 4
14 37 2
14 43 4
14 47 4
14 50 2
14 53 3
15 0 3
15 19 3
15 20 4
15 23 2
15 27 3
15 35 2
15 37 3
15 47 5
16 19 4
16 23 2
16 24 5
16 27 2
16 38 5
17 2 5
17 11 4
17 15 5
17 50 3
18 11 5
18 15 3
18 24 3
18 39 5
18 56 4
18 59 5
19 11 5
19 15 5
19 20 2
19 26 4
19 51 4
19 59 4
20 5 4
20 6 4
20 7 4
20 10 3
20 11 4
20 15 4
20 37 5
20 40 4
20 52 2
20 59 3
21 2 2
21 7 3
21 30 5
21 39 3
21 45 3
21 48 2
21 53 4
22 4 4
22 7 2
22 16 4
22 28 2
23 25 3
23 29 2
23 45 4
23 46 5
23 57 4
23 59 4
24 12 3
24 28 5
24 57 2
25 4 2
25 5 3
25 6 4
25 7 2
25 27 4
25 35 5
25 37 3
25 41 3
25 53 3
25 56 4
26 1 5
26 14 2
26 20 3
26 25 3
26 30 3
26 38 5
27 1 2
27 5 4
27 11 2
27 14 3
27 18 2
27 23 2
27 38 3
27 50 2
27 52 2
27 59 5
28 14 2
28 24 5
28 28 2
28 44 3
28 50 3
28 58 4
28 59 3
29 4 2
29 10 5
29 14 4
29 15 2
29 31 3
29 41 3
29 49 4
30 1 4
30 4 3
30 8 2
30 13 5
30 30 3
30 38 4
30 43 3
30 47 3
30 53 3
30 55 3
30 56 2
30 59 2
31 0 5
31 5 3
31 10 2
31 17 5
31 27 4
31 37 2
31 39 3
31 44 4
31 57 4
32 8 3
32 20 3
32 30 5
32 40 2
32 56 5
33 14 3
33 17 4
33 21 3
33 33 3
33 43 4
33 45 3
33 46 4
33 52 5
33 59 5
34 8 4
34 10 4
34 17 2
34 23 5
34 55 5
34 59 5
35 4 2
35 15 3
35 19 5
35 20 2
35 22 5
35 25 2
35 31 5
35 48 2
36 1 4
36 54 3
36 56 2
37 1 5
37 4 2
37 6 3
37 12 4
37 37 5
37 41 5
37 44 2
37 48 2
37 56 2
38 28 2
38 32 3
38 41 5
38 42 5
38 47 5
38 55 2
39 0 4
39 3 2
39 8 2
39 13 5
39 25 3
39 54 3
40 4 2
40 15 3
40 34 4
40 48 5
40 50 4
40 54 4
41 6 4
41 25 4
41 29 4
41 36 5
41 39 4
41 43 4
41 48 4
41 58 4
42 16 2
42 18 3
42 30 5
42 31 4
42 46 2
42 48 2
43 31 2
43 40 2
43 42 2
43 48 5
44 15 4
44 23 3
44 24 5
44 30 2
44 35 2
44 41 5
44 45 4
44 50 2
44 51 3
44 53 3
45 18 3
45 22 5
45 25 5
45 27 2
45 32 3
45 35 4
45 36 2
45 57 4
46 0 4
46 9 5
46 11 2
46 13 4
46 37 3
46 45 3
46 52 2
47 21 2
47 23 4
47 26 2
47 29 5
47 40 2
47 41 3
47 49 3
47 50 4
47 56 5
48 8 3
48 9 2
48 25 5
48 28 4
48 34 2
49 32 5
49 40 5
50 43 2
50 46 5
50 54 5
50 59 3
51 10 4
51 11 3
51 18 2
51 54 4
52 0 4
52 4 4
52 7 3
52 11 2
52 22 2
52 26 2
52 49 3
53 2 3
53 8 4
53 10 2
53 23 4
53 31 3
53 32 3
53 39 4
53 44 2
53 52 2
54 3 3
54 30 4
54 35 4
54 39 4
55 1 3
55 9 5
55 14 4
55 36 2
55 37 5
55 41 4
55 42 2
55 57 3
56 17 5
56 20 3
56 25 3
56 49 4
56 51 4
57 14 2
57 22 2
57 42 5
57 44 3
58 0 2
58 2 4
58 17 2
58 18 4
58 40 2
58 49 4
59 2 4
59 9 4
59 15 3
59 20 3
59 33 2
59 55 5
59 57 2
")
    (main)))