Problem:


Score : 100 points

Problem Statement

You are given a string of length N. Calculate the number of distinct substrings of S.

Constraints

1 \leq N \leq 500,000

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

abcbcba

Sample Output 1

21

Sample Input 2

mississippi

Sample Output 2

53

Sample Input 3

ababacaca

Sample Output 3

33

Sample Input 4

aaaaa

Sample Output 4

5



Sample input:
abcbcba


Sample output:
21

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
from libcpp.vector cimport vector
from libcpp.string cimport string
cdef extern from "<atcoder/string>" namespace "atcoder" nogil:
    cdef vector[int] suffix_array(string s)
    cdef vector[int] suffix_array[T](vector[T] s)
    cdef vector[int] suffix_array(vector[int] s, int upper)
    cdef vector[int] lcp_array(string s, vector[int] sa)
    cdef vector[int] lcp_array[T](vector[T] s, vector[int] sa)
    cdef vector[int] z_algorithm(string s)
    cdef vector[int] z_algorithm[T](vector[T] s)
cdef string s = input().encode()
cdef long n = s.length()
cdef vector[int] sa = suffix_array(s)
cdef vector[int] la = lcp_array(s, sa)
cdef long a = n * (n + 1) // 2
for i in range(n - 1): a -= la[i]
print(a)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve