Description

Given a string $S$ of length $n$, let $T_i$ denote the suffix starting from its $i$-th character. Compute

$$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$

where $\text{len}(a)$ denotes the length of string $a$, and $\text{lcp}(a,b)$ denotes the longest common prefix of strings $a$ and $b$.

Input Format

One line, a string $S$.

Output Format

One line, an integer representing the required value.

cacao

54

Hint

Constraints

• For $100\%$ of the testdata, it is guaranteed that $2\le n\le 500000$, and all characters in $S$ are lowercase letters.

Translated by ChatGPT 5