Ancient Substring MST

Given a string \(S\) consisting of lowercase letters, consider all of its distinct non-empty substrings. Each substring is treated as a vertex. For any two distinct substrings \(u\) and \(v\), define the edge weight between them as

\(\text{weight}(u,v)=\text{occ}(u)+\text{occ}(v)+\text{LCP}(u,v)\)

where \(\text{occ}(x)\) is the number of occurrences of substring \(x\) in \(S\), and \(\text{LCP}(u,v)\) denotes the length of the longest common prefix between \(u\) and \(v\). If we form a complete graph with these vertices and edge weights, the substrings can be "connected" into a sentence that corresponds to one of the minimum spanning trees (MST) of this graph. Your task is to compute the sum of the edge weights in the MST of this complete graph.

Note: Two substrings are considered essentially different if they differ in length or if, when of the same length, they differ in at least one character.

inputFormat

The input consists of a single line containing the string \(S\) (only lowercase letters).

outputFormat

Output a single integer, which is the total weight of the minimum spanning tree (MST) constructed on all distinct non-empty substrings of \(S\).

sample

a

0