;; -*- 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
           #\# #\> (lambda (s c p) (declare (ignore c p)) (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
;;;
;;; Bit-reversal operation
;;; Reference: https://stackoverflow.com/questions/746171/efficient-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c
;;;

(declaim ((simple-array (unsigned-byte 16) (65536)) *bit-reverse-table*))
(defparameter *bit-reverse-table*
  (make-array 65536 :element-type '(unsigned-byte 16)))

(dotimes (idx (length *bit-reverse-table*))
  (let ((table *bit-reverse-table*)
        (x idx))
    (setq x (logior (ash (logand x #xaaaa) -1)
                    (ash (logand x #x5555) 1)))
    (setq x (logior (ash (logand x #xcccc) -2)
                    (ash (logand x #x3333) 2)))
    (setq x (logior (ash (logand x #xf0f0) -4)
                    (ash (logand x #x0f0f) 4)))
    (setq x (logior (ash x -8) (ldb (byte 16 0) (ash x 8))))
    (setf (aref table idx) x)))

(declaim (inline logreverse))
(defun logreverse (x size)
  "Returns the bit-reversal in the range [0, SIZE) of X."
  (declare ((unsigned-byte 64) x)
           ((integer 0 64) size))
  (let ((table *bit-reverse-table*))
    (ash (logior
          (ash (aref table (logand x #xffff)) 48)
          (ash (aref table (logand (ash x -16) #xffff)) 32)
          (ash (aref table (logand (ash x -32) #xffff)) 16)
          (aref table (logand (ash x -48) #xffff)))
         (- size 64))))

;; Below is a somewhat slower but space efficient bit-reversal
;; (declaim (inline logreverse))
;; (defun logreverse (x size)
;;   "Returns the bit-reversal in the range [0, SIZE) of X."
;;   (declare ((unsigned-byte 64) x)
;;            ((integer 0 64) size))
;;   (if (<= size 8)
;;       (ash (mod (logand (* x #x0202020202) #x010884422010) 1023)
;;            (- size 8))
;;       (progn
;;         (setq x (logior (ash (logand x #xaaaaaaaaaaaaaaaa) -1)
;;                         (ash (logand x #x5555555555555555) 1)))
;;         (setq x (logior (ash (logand x #xcccccccccccccccc) -2)
;;                         (ash (logand x #x3333333333333333) 2)))
;;         (setq x (logior (ash (logand x #xf0f0f0f0f0f0f0f0) -4)
;;                         (ash (logand x #x0f0f0f0f0f0f0f0f) 4)))
;;         (setq x (logior (ash (logand x #xff00ff00ff00ff00) -8)
;;                         (ash (logand x #x00ff00ff00ff00ff) 8)))
;;         (setq x (logior (ash (logand x #xffff0000ffff0000) -16)
;;                         (ash (logand x #x0000ffff0000ffff) 16)))
;;         (ash (logior (ash x -32) (ldb (byte 64 0) (ash x 32)))
;;              (- size 64)))))

;;;
;;; Fast operations on GF(2)
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (assert (= sb-vm:n-word-bits 64)))

(defun f2-echelon! (matrix &optional extended)
  "Returns the row echelon form of MATRIX by gaussian elimination on GF(2). If
EXTENDED is true, the last column is regarded as the right hand side of the
linear equations and is not eliminated. This function destructively modifies
MATRIX.

The width of MATRIX must be multiple of 64."
  (declare (optimize (speed 3))
           ((simple-array bit (* *)) matrix))
  (destructuring-bind (m n) (array-dimensions matrix)
    (declare (optimize (safety 0))
             ((integer 0 #.most-positive-fixnum) m n))
    (multiple-value-bind (n/64 rem) (floor n 64)
      (assert (zerop rem))
      (let* ((storage (array-storage-vector matrix))
             (rank 0))
        (declare (fixnum rank))
        (dotimes (target-col (if extended (- n 1) n))
          (let* ((pivot-row (do ((i rank (+ 1 i)))
                                ((= i m) -1)
                              (unless (zerop (aref matrix i target-col))
                                (return i)))))
            (when (>= pivot-row 0)
              (let ((pivot-row/64 (floor (array-row-major-index matrix pivot-row 0) 64))
                    (rank-row/64 (floor (array-row-major-index matrix rank 0) 64)))
                ;; swap rows
                (loop for k from 0 below n/64
                      do (rotatef (sb-kernel:%vector-raw-bits storage (+ rank-row/64 k))
                                  (sb-kernel:%vector-raw-bits storage (+ pivot-row/64 k))))
                ;; eliminate the column
                (dotimes (i m)
                  (unless (or (= i rank) (zerop (aref matrix i target-col)))
                    (loop with base/64 = (floor (array-row-major-index matrix i 0) 64)
                          for k below n/64
                          do (setf (sb-kernel:%vector-raw-bits storage (+ base/64 k))
                                   (logxor (sb-kernel:%vector-raw-bits storage (+ base/64 k))
                                           (sb-kernel:%vector-raw-bits storage (+ rank-row/64 k))))))))
              (incf rank))))
        (values matrix rank)))))

(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 (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(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)))

(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
;;;

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (as (make-array n :element-type 'uint62))
         (mat (make-array (list n 64) :element-type 'bit))
         (storage (array-storage-vector mat)))
    (declare (uint32 n))
    (dotimes (i n)
      (setf (aref as i) (read-fixnum)))
    (let* ((total-xor (reduce #'logxor as)))
      (declare (uint62 total-xor))
      (dotimes (i n)
        (setf (sb-kernel:%vector-raw-bits storage i)
              (logreverse (logandc2 (aref as i) total-xor) 64)))
      (f2-echelon! mat)
      (let ((rxor 0))
        (declare (uint62 rxor))
        (dotimes (i n)
          (setf rxor (logxor rxor (logreverse (sb-kernel:%vector-raw-bits storage i) 64))))
        (println (+ (logior rxor total-xor) rxor))))))

#-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:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+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 "100000~%")
    (dotimes (_ 100000)
      (println (random #.(expt 2 60)) 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 "3
3 6 5
"
    "12
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
23 36 66 65
"
    "188
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181
"
    "2012721721873704572
")))


Measured memory_bytes: 17508