(in-package :cl-user)
(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)) `(values ,(read s nil nil t)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)

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

(defconstant +mod+ 1000000007)

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

;; BEGIN_INSERTED_CONTENTS
;;;
;;; SA-IS
;;; Reference:
;;; https://github.com/atcoder/ac-library/blob/master/atcoder/string.hpp
;;;

(defpackage :cp/suffix-array
  (:use :cl)
  (:export #:sa-int #:sa-vector #:make-suffix-array #:make-lcp-array))
(in-package :cp/suffix-array)

(deftype sa-int () '(signed-byte 32))
(deftype sa-vector () '(simple-array sa-int (*)))

(declaim (ftype (function * (values sa-vector &optional)) %sa-is))
(defun %sa-is (vector size)
  (declare #.cl-user::opt
           (sa-vector vector)
           ((integer 0 #.(- (ash 1 31) 1)) size))
  (let* ((n (length vector))
         (sa (make-array n :element-type 'sa-int :initial-element 0))
         (ls (make-array n :element-type 'bit :initial-element 0)))
    (when (<= n 1)
      (return-from %sa-is sa))
    (loop for i from (- n 2) downto 0
          do (setf (aref ls i)
                   (cond ((= (aref vector i) (aref vector (+ i 1)))
                          (aref ls (+ i 1)))
                         ((< (aref vector i) (aref vector (+ i 1)))
                          1)
                         (t 0))))
    (let ((sum-l (make-array (+ size 1) :element-type 'sa-int :initial-element 0))
          (sum-s (make-array (+ size 1) :element-type 'sa-int :initial-element 0)))
      (dotimes (i n)
        (if (zerop (aref ls i))
            (incf (aref sum-s (aref vector i)))
            (incf (aref sum-l (+ 1 (aref vector i))))))
      (dotimes (i (+ size 1))
        (incf (aref sum-s i) (aref sum-l i))
        (when (< i size)
          (incf (aref sum-l (+ i 1)) (aref sum-s i))))
      (labels
          ((induce! (lms)
             (declare (sa-vector lms))
             (fill sa -1)
             (let ((buf (copy-seq sum-s)))
               (loop for d across lms
                     unless (= d n)
                     do (setf (aref sa (aref buf (aref vector d))) d)
                        (incf (aref buf (aref vector d))))
               (replace buf sum-l)
               (setf (aref sa (aref buf (aref vector (- n 1)))) (- n 1))
               (incf (aref buf (aref vector (- n 1))))
               (loop for i below n
                     for v = (aref sa i)
                     when (and (>= v 1) (= 0 (aref ls (- v 1))))
                     do (setf (aref sa (aref buf (aref vector (- v 1)))) (- v 1))
                        (incf (aref buf (aref vector (- v 1)))))
               (replace buf sum-l)
               (loop for i from (- n 1) downto 0
                     for v = (aref sa i)
                     when (and (>= v 1) (= 1 (aref ls (- v 1))))
                     do (decf (aref buf (+ 1 (aref vector (- v 1)))))
                        (setf (aref sa (aref buf (+ 1 (aref vector (- v 1))))) (- v 1))))))
        (let ((lms-map (make-array (+ n 1) :element-type 'sa-int :initial-element -1))
              (m 0))
          (declare (sa-int m))
          (loop for i from 1 below n
                when (and (= 0 (aref ls (- i 1)))
                          (= 1 (aref ls i)))
                do (setf (aref lms-map i) m)
                   (incf m))
          (let ((lms (make-array m :element-type 'sa-int :initial-element 0)))
            (let ((end 0))
              (declare (sa-int end))
              (loop for i from 1 below n
                    when (and (= 0 (aref ls (- i 1)))
                              (= 1 (aref ls i)))
                    do (setf (aref lms end) i)
                       (incf end))
              (setq lms (adjust-array lms end)))
            (induce! lms)
            (unless (zerop m)
              (let ((sorted-lms (make-array m :element-type 'sa-int :initial-element 0))
                    (rec-vector (make-array m :element-type 'sa-int :initial-element 0))
                    (rec-size 0))
                (declare (sa-int rec-size)
                         (sa-vector sorted-lms))
                (let ((end 0))
                  (declare (sa-int end))
                  (loop for v across sa
                        unless (= -1 (aref lms-map v))
                        do (setf (aref sorted-lms end) v)
                           (incf end))
                  (setq sorted-lms (adjust-array sorted-lms end)))
                (setf (aref rec-vector (aref lms-map (aref sorted-lms 0))) 0)
                (loop for i from 1 below m
                      for l = (aref sorted-lms (- i 1))
                      for r = (aref sorted-lms i)
                      for end-l = (if (< (+ 1 (aref lms-map l)) m)
                                      (aref lms (+ 1 (aref lms-map l)))
                                      n)
                      for end-r = (if (< (+ 1 (aref lms-map r)) m)
                                      (aref lms (+ 1 (aref lms-map r)))
                                      n)
                      for same = t
                      when (= (- end-l l) (- end-r r))
                      do (loop while (and (< l end-l) (= (aref vector l) (aref vector r)))
                               do (incf l)
                                  (incf r))
                         (when (or (= l n) (/= (aref vector l) (aref vector r)))
                           (setq same nil))
                      else
                      do (setq same nil)
                      unless same
                      do (incf rec-size)
                      do (setf (aref rec-vector (aref lms-map (aref sorted-lms i)))
                               rec-size))
                (let ((rec-sa (%sa-is rec-vector rec-size)))
                  (dotimes (i m)
                    (setf (aref sorted-lms i) (aref lms (aref rec-sa i))))
                  (induce! sorted-lms))))))))
    sa))

(declaim (inline make-suffix-array))
(defun make-suffix-array (vector &key key order alphabet-size)
  "Returns the suffix array of VECTOR. The order of elements is determined by
KEY or ORDER.

KEY := function that returns a non-negative integer less than 2^31
ORDER := strict total order on the elements of VECTOR"
  (declare (vector vector)
           ((or null (integer 1 #.(- (ash 1 31) 1))) alphabet-size))
  (assert (and (or key order)
               (not (and key order))))
  (if order
      (let* ((n (length vector))
             (ords (make-array n :element-type 'sa-int :initial-element 0)))
        (dotimes (i n)
          (setf (aref ords i) i))
        (setq ords (sort ords order :key (lambda (i) (aref vector i))))
        (let* ((vector2 (make-array n :element-type 'sa-int :initial-element 0))
               (end 0))
          (dotimes (i n)
            (when (and (> i 0)
                       (funcall order
                                (aref vector (aref ords (- i 1)))
                                (aref vector (aref ords i))))
              (incf end))
            (setf (aref vector2 (aref ords i)) end))
          (%sa-is vector2 end)))
      (%sa-is (map 'sa-vector (or key #'identity) vector)
              (or alphabet-size (+ (reduce #'max vector :key key) 1)))))

(declaim (inline make-lcp-array))
(defun make-lcp-array (vector sa &key (test #'eql))
  "Returns the LCP array."
  (declare (vector vector)
           (sa-vector sa))
  (let* ((n (length vector))
         (rev (make-array n :element-type 'sa-int :initial-element 0))
         (lcp (make-array (- n 1) :element-type 'sa-int :initial-element 0))
         (height 0))
    (declare (sa-int height))
    (assert (and (= n (length sa)) (>= n 1)))
    (dotimes (i n)
      (setf (aref rev (aref sa i)) i))
    (dotimes (i n)
      (when (> height 0)
        (decf height))
      (unless (zerop (aref rev i))
        (let  ((j (aref sa (- (aref rev i) 1))))
          (loop while (and (< (+ j height) n)
                           (< (+ i height) n)
                           (funcall test
                                    (aref vector (+ j height))
                                    (aref vector (+ i height))))
                do (incf height))
          (setf (aref lcp (- (aref rev i) 1)) height))))
    lcp))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/suffix-array :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (declare #.cl-user::opt)
  (let* ((s (read-line))
         (n (length s))
         (sa (make-suffix-array s :key (lambda (c) (- (char-code c) 97))
                                  :alphabet-size 26))
         (lcps (make-lcp-array s sa :test #'eq)))
    (declare (uint31 n)
             (simple-string s))
    (println (loop for i below n
                   for pos = (aref sa i)
                   sum (if (zerop i)
                           (- n pos)
                           (- n pos (aref lcps (- i 1))))
                   of-type uint62))))

#-swank (main)

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

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    #+os-windows (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)
    #+os-unix (run-program "xsel" '("-b" "-o") :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* (or out (make-string-output-stream)))
         (res (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))))))
    (if out res (get-output-stream-string *standard-output*))))

#+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)))

#-swank
(eval-when (:compile-toplevel)
  (when (and (boundp 'sb-c::*compiler-warning-count*)
             (> sb-c::*compiler-warning-count* 0))
    (sb-ext:quit :unix-status 1)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (5am:is
   (equal "21
"
          (run "abcbcba
" nil)))
  (5am:is
   (equal "53
"
          (run "mississippi
" nil)))
  (5am:is
   (equal "33
"
          (run "ababacaca
" nil)))
  (5am:is
   (equal "5
"
          (run "aaaaa
" nil))))


Measured memory_bytes: 47304