結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 motoshira
|
| 提出日時 | 2023-07-02 13:44:41 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 25,343 bytes |
| コンパイル時間 | 441 ms |
| コンパイル使用メモリ | 62,180 KB |
| 実行使用メモリ | 226,044 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-07-02 13:45:28 |
| 合計ジャッジ時間 | 39,986 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | WA | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | WA | - |
| testcase_71 | WA | - |
| testcase_72 | WA | - |
| testcase_73 | WA | - |
| testcase_74 | WA | - |
| testcase_75 | WA | - |
| testcase_76 | WA | - |
| testcase_77 | WA | - |
| testcase_78 | WA | - |
| testcase_79 | WA | - |
| testcase_80 | WA | - |
| testcase_81 | WA | - |
| testcase_82 | WA | - |
| testcase_83 | WA | - |
| testcase_84 | WA | - |
| testcase_85 | WA | - |
| testcase_86 | WA | - |
| testcase_87 | WA | - |
| testcase_88 | WA | - |
| testcase_89 | WA | - |
| testcase_90 | WA | - |
| testcase_91 | WA | - |
| testcase_92 | WA | - |
| testcase_93 | WA | - |
| testcase_94 | WA | - |
| testcase_95 | WA | - |
| testcase_96 | WA | - |
| testcase_97 | WA | - |
| testcase_98 | WA | - |
| testcase_99 | WA | - |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 02 JUL 2023 01:44:40 PM): ; processing (IN-PACKAGE #:CL-USER) ; processing (DECLAIM (OPTIMIZE # ...)) ; processing (DECLAIM (MUFFLE-CONDITIONS COMPILER-NOTE)) ; processing (DISABLE-DEBUGGER) ; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...) ; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...) ; processing (DEFPACKAGE RANDOMIZED-HEAP ...) ; processing (IN-PACKAGE #:RANDOMIZED-HEAP) ; processing (DEFVAR *OPT* ...) ; processing (DECLAIM (INLINE %MAKE-NODE ...)) ; processing (DEFSTRUCT (NODE # ...) ...) ; processing (DEFSTRUCT (RANDOMIZED-HEAP #) ...) ; processing (DEFUN COUNT ...) ; processing (DECLAIM (INLINE %DIRECTION)) ; processing (DEFUN %DIRECTION ...) ; processing (DEFUN MELD ...) ; processing (DECLAIM (INLINE PEAK)) ; processing (DEFUN PEAK ...) ; processing (DEFUN EMPTY-P ...) ; processing (DECLAIM (INLINE POP! ...)) ; processing (DEFUN POP! ...) ; processing (DEFUN PUSH! ...) ; processing (DEFMACRO DO-ALL-KVS ...) ; processing (DEFUN PRUNE! ...) ; processing (DEFPACKAGE MACRO ...) ; processing (IN-PACKAGE MACRO) ; processing (DEFMACRO WHILE ...) ; processing (DEFMACRO EVAL-ALWAYS ...) ; processing (DEFPACKAGE UTIL ...) ; processing (IN-PACKAGE UTIL) ; processing (DEFUN MANHATTAN-DIST ...) ; processing (SB-INT:DEFCONSTANT-EQX +DIR-DY-DX+ ...) ; processing (SB-INT:DEFCONSTANT-EQX +DY-DX+ ...) ; processing (SB-INT:DEFCONSTANT-EQX +DIRS+ ...) ; processing (DEFUN COORDS->DIR ...) ; processing (IN-PACKAGE CL-USER) ; processing (DEFCONSTANT +GRID-SIZE+ ...) ; processing (DEFCONSTANT +VITAL+ ...) ; processing (DEFSTRUCT TRAP ...) ; processing (DEFSTRUCT CHECKPOINT ...) ; processing (DEFUN GET-TRAP-FACTOR ...) ; processing (DEFSTRUCT (EDGE-BETWEEN-CHECKPOINTS #) ...) ; processing (DEFUN GET-ESTIMATED-COST-EDGES-BETWEEN-CHECKPOINTS ...) ; processing (DEFUN GET-ESTIMATED-COSTS-AND-DIRS-BETWEEN-CHECKPOINTS ...) ; processing (DEFUN FIND-CHARS ...) ; processing (DEFUN ORDERS->DIRS ...) ; processing (DEFUN VALIDAT
ソースコード
(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))
(defstruct (edge-between-checkpoints (:conc-name edge-))
(dist-id nil :type fixnum)
(estimated-cost nil :type single-float)
(dirs nil :type list))
(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)))
;; 距離15以下でたどり着けるものと辺でつなぐ
(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 16))
(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 16)))
do (setf #2# (+ cost (aref trap-factors ny nx)))
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)))))
(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 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)))))
#> checkpoints
(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))
(fixed (list start key goal))
(orders (vector start key goal))
(cost (loop for (cp1 cp2) on orders by #'cdr
when cp2
sum (car (aref costs-and-dirs
(checkpoint-id cp1)
(checkpoint-id cp2))))))
;; #>costs-and-dirs
(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 (1- 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) (- h 500)))
(setf orders (concatenate 'vector
(subseq orders 0 insert-index)
(vector cp)
(subseq orders insert-index)))
(incf cost min-cost-diff)))))
#> (cost orders)
(let ((dirs (orders->dirs orders costs-and-dirs)))
#+swank
(validate-dirs grid dirs)
(dolist (dir dirs)
(format t "M ~a~%" dir))))))
#-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)))