結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
|
提出日時 | 2023-07-02 16:07:29 |
言語 | Common Lisp (sbcl 2.5.0) |
結果 |
AC
|
実行時間 | 2,061 ms / 3,000 ms |
コード長 | 28,335 bytes |
コンパイル時間 | 1,298 ms |
コンパイル使用メモリ | 71,428 KB |
実行使用メモリ | 173,744 KB |
スコア | 90,600 |
最終ジャッジ日時 | 2023-07-02 16:09:54 |
合計ジャッジ時間 | 139,387 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 02 JUL 2023 04:07:29 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 (DEFUN GET-REAL-TRAP-FACTOR ...) ; processing (DEFSTRUCT (EDGE-BETWEEN-CHECKPOINTS #) ...) ; processing (DEFCONSTANT +COST-THRESHOLD-BETWEEN-CHECKPOINTS+ ...) ; processing (DEFUN GET-ESTIMATED-COST-EDGES-BETWEEN-CHECKPOINTS ...) ; processing (DEFUN GET-ESTIMATED-COSTS-AND-DIRS-BETWEEN-CHEC
ソースコード
(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)rcomparator))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 lr(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)),setternil)))))(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 '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 (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#nynx(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 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 10)(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))(fixed (list start key goal)));; #>costs-and-dirs(loop repeat 10 for est-vital downfrom (- h 300) by 80 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 est-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 (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-diffinsert-index i))(when (and (>= insert-index 1)(<= (+ cost min-cost-diff) est-vital))(setf orders (concatenate 'vector(subseq orders 0 insert-index)(vector cp)(subseq orders insert-index)))(incf cost min-cost-diff)))))(let* ((dirs (orders->dirs orders costs-and-dirs))(insts (get-insts grid dirs traps)))(when insts#> (est-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..EJE..#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.EJ#..#....#.#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.#EE#...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..3740 18 50 24 50 25 20 30 30 34 20 45 30 46 41 1 31 14 51 19 22 37 52 41 53 3 33 8 43 17 33 27 34 11 24 42 44 53 25 9 45 10 25 24 35 40 55 43 25 58 56 30 26 38 56 50 56 56 57 14 27 15 57 24 57 26 47 31 57 33 47 40 38 0 58 2 58 18 58 22 38 27 38 28 58 46 28 51 59 12 39 16 39 23 59 39 410 1 510 5 210 26 510 28 310 51 410 54 311 30 212 0 412 7 412 24 412 40 512 41 412 51 512 57 413 0 413 20 213 28 213 39 413 54 213 59 514 1 514 5 414 10 414 13 514 18 214 22 414 37 214 43 414 47 414 50 214 53 315 0 315 19 315 20 415 23 215 27 315 35 215 37 315 47 516 19 416 23 216 24 516 27 216 38 517 2 517 11 417 15 517 50 318 11 518 15 318 24 318 39 518 56 418 59 519 11 519 15 519 20 219 26 419 51 419 59 420 5 420 6 420 7 420 10 320 11 420 15 420 37 520 40 420 52 220 59 321 2 221 7 321 30 521 39 321 45 321 48 221 53 422 4 422 7 222 16 422 28 223 25 323 29 223 45 423 46 523 57 423 59 424 12 324 28 524 57 225 4 225 5 325 6 425 7 225 27 425 35 525 37 325 41 325 53 325 56 426 1 526 14 226 20 326 25 326 30 326 38 527 1 227 5 427 11 227 14 327 18 227 23 227 38 327 50 227 52 227 59 528 14 228 24 528 28 228 44 328 50 328 58 428 59 329 4 229 10 529 14 429 15 229 31 329 41 329 49 430 1 430 4 330 8 230 13 530 30 330 38 430 43 330 47 330 53 330 55 330 56 230 59 231 0 531 5 331 10 231 17 531 27 431 37 231 39 331 44 431 57 432 8 332 20 332 30 532 40 232 56 533 14 333 17 433 21 333 33 333 43 433 45 333 46 433 52 533 59 534 8 434 10 434 17 234 23 534 55 534 59 535 4 235 15 335 19 535 20 235 22 535 25 235 31 535 48 236 1 436 54 336 56 237 1 537 4 237 6 337 12 437 37 537 41 537 44 237 48 237 56 238 28 238 32 338 41 538 42 538 47 538 55 239 0 439 3 239 8 239 13 539 25 339 54 340 4 240 15 340 34 440 48 540 50 440 54 441 6 441 25 441 29 441 36 541 39 441 43 441 48 441 58 442 16 242 18 342 30 542 31 442 46 242 48 243 31 243 40 243 42 243 48 544 15 444 23 344 24 544 30 244 35 244 41 544 45 444 50 244 51 344 53 345 18 345 22 545 25 545 27 245 32 345 35 445 36 245 57 446 0 446 9 546 11 246 13 446 37 346 45 346 52 247 21 247 23 447 26 247 29 547 40 247 41 347 49 347 50 447 56 548 8 348 9 248 25 548 28 448 34 249 32 549 40 550 43 250 46 550 54 550 59 351 10 451 11 351 18 251 54 452 0 452 4 452 7 352 11 252 22 252 26 252 49 353 2 353 8 453 10 253 23 453 31 353 32 353 39 453 44 253 52 254 3 354 30 454 35 454 39 455 1 355 9 555 14 455 36 255 37 555 41 455 42 255 57 356 17 556 20 356 25 356 49 456 51 457 14 257 22 257 42 557 44 358 0 258 2 458 17 258 18 458 40 258 49 459 2 459 9 459 15 359 20 359 33 259 55 559 57 2")(main)))