;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(defmacro with-buffered-stdout (&body body)
  "Buffers all outputs to *STANDARD-OUTPUT* in BODY and flushes them to
*STANDARD-OUTPUT* after BODY has been done (without error). Note that only
BASE-CHAR is allowed."
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defparameter *plan3* #2A((#\a #\a #\.)
                          (#\. #\. #\b)
                          (#\. #\. #\b)))
(defparameter *plan4* #2A((#\a #\a #\b #\c)
                          (#\d #\d #\b #\c)
                          (#\e #\f #\g #\g)
                          (#\e #\f #\h #\h)))
(defparameter *plan5* #2A((#\a #\. #\b #\c #\c)
                          (#\a #\. #\b #\. #\d)
                          (#\e #\e #\. #\f #\d)
                          (#\. #\g #\g #\f #\h)
                          (#\i #\i #\j #\j #\h)))
(defparameter *plan6* #2A((#\. #\a #\b #\. #\c #\c)
                          (#\. #\a #\b #\. #\. #\d)
                          (#\e #\e #\. #\f #\. #\d)
                          (#\g #\g #\. #\f #\h #\.)
                          (#\i #\. #\j #\j #\h #\.)
                          (#\i #\. #\k #\k #\l #\l)))
(defparameter *plan7* #2A((#\a #\. #\b #\. #\. #\c #\c)
                          (#\a #\. #\b #\. #\d #\. #\.)
                          (#\e #\e #\. #\. #\d #\. #\f)
                          (#\g #\g #\h #\h #\. #\. #\f)
                          (#\. #\. #\i #\j #\j #\k #\k)
                          (#\. #\l #\i #\. #\. #\m #\.)
                          (#\. #\l #\. #\n #\n #\m #\.)))
(defun test (n target)
  (let ((plan (make-array (list n n) :element-type 'uint32 :initial-element 0))
        (vquals (make-array n :element-type 'uint32 :initial-element 0))
        (hquals (make-array n :element-type 'uint32 :initial-element 0)))
    (loop
      named outer
      do (fill (array-storage-vector plan) 0)
      (fill vquals 0)
      (fill hquals 0)
      (loop named inter
            for i from 1 to (* n n)
            do (when (and (loop for q across vquals
                                do (when (> q target)
                                     (return-from inter))
                                   (when (< q target)
                                     (return))
                                finally (return t))
                          (loop for q across hquals
                                do (when (> q target)
                                     (return-from inter))
                                   (when (< q target)
                                     (return))
                                finally (return t)))
                 (return-from outer))
               (let ((y (random n))
                     (x (random n))
                     (dir (random 2)))
                 (when (and (= dir 0) (< (+ y 1) n)
                            (zerop (aref plan y x))
                            (zerop (aref plan (+ y 1) x)))
                   (setf (aref plan y x) i
                         (aref plan (+ y 1) x) i)
                   (incf (aref hquals y))
                   (incf (aref hquals (+ y 1)))
                   (incf (aref vquals x)))
                 (when (and (= dir 1) (< (+ x 1) n)
                            (zerop (aref plan y x))
                            (zerop (aref plan y (+ x 1))))
                   (setf (aref plan y x) i
                         (aref plan y (+ x 1)) i)
                   (incf (aref hquals y))
                   (incf (aref vquals x))
                   (incf (aref vquals (+ x 1)))))))
    (let ((res (make-array (list n n) :element-type 'base-char :initial-element #\.))
          (table (make-hash-table))
          (offset 0))
      (dotimes (i n)
        (dotimes (j n)
          (when (> (aref plan i j) 0)
            (let ((c (or (gethash (aref plan i j) table)
                         (prog1 (code-char (+ 97 offset))
                           (incf offset)))))
              (setf (gethash (aref plan i j) table) c)
              (setf (aref res i j) c)))))
      res)))

(defun main ()
  (let* ((n (read)))
    (labels ((%print (mat)
               (with-buffered-stdout
                 (dotimes (i n)
                   (dotimes (j n (terpri))
                     (write-char (aref mat i j)))))))
      (cond ((= n 2) (println -1))
            ((= n 3) (%print *plan3*))
            ((= n 4) (%print *plan4*))
            (t
             (multiple-value-bind (factor rem) (floor n 4)
               (decf factor)
               (incf rem 4)
               (let ((res (make-array (list n n)
                                      :element-type 'base-char
                                      :initial-element #\.)))
                 (loop
                   for d below factor
                   do (dotimes (i 4)
                        (dotimes (j 4)
                          (setf (aref res (+ (* 4 d) i) (+ (* 4 d) j))
                                (aref *plan4* i j)))))
                 (let ((remplan (ecase rem
                                  (0)
                                  (4 *plan4*)
                                  (5 *plan5*)
                                  (6 *plan6*)
                                  (7 *plan7*))))
                   (dotimes (i (array-dimension remplan 0))
                     (dotimes (j (array-dimension remplan 1))
                       (setf (aref res (+ (* 4 factor) i) (+ (* 4 factor) j))
                             (aref remplan i j)))))
                 (%print res))))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6
"
    "aabb..
b..zz.
ba....
.a..aa
..a..b
..a..b
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "2
"
    "-1
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6
"
    "aabb..
b..zz.
ba....
.a..aa
..a..b
..a..b
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "2
"
    "-1
")))


Measured memory_bytes: 32232