Illyasviel："你喜欢字符串吗？"
Star-dust："喜欢！"
Illyasviel："那来求每个子串两两之间的最长公共前缀的长度之和吧！"
Star-dust："好啊，但求一个不够过瘾，对所有后缀都求一遍吧。"
定义一个函数 $f(S)$ 如下：
$S$ 是一个字符串，令 $n$ 为此字符串的长度，于是 $S$ 会有 $\frac{n \times (n+1)}{2}$ 个非空子串，那么选 $S$ 的两个有序的非空子串对，就会有 $(\frac{n \times (n+1)}{2})^2$ 种组合，$f(S)$ 的值就是这 $(\frac{n \times (n+1)}{2})^2$ 个组合的两个字串间最长公共前缀的和。
例如 $f($"ab"$)$ 的计算方法如下：
"ab" 的子串总共有 "b","ba","a" 三个。
"b" 和 "b" 的最长公共前缀是 $1$。
"b" 和 "ba" 的最长公共前缀是 $1$。
"b" 和 "a" 的最长公共前缀是 $0$。
"ba" 和 "b" 的最长公共前缀是 $1$。
"ba" 和 "ba" 的最长公共前缀是 $2$。
"ba" 和 "a" 的最长公共前缀是 $0$。
"a" 和 "b" 的最长公共前缀是 $0$。
"a" 和 "ba" 的最长公共前缀是 $0$。
"a" 和 "a" 的最长公共前缀是 $1$。
所以 $f($"ab"$) = 1+1+0+1+2+0+0+0+1=6$ 。
现在给定你一个字符串 $T$，其长度为 $m$，对于每个 $i$ 从 $1$ 至 $m$，都计算出 $f(T_{i..m})$ ($T_{i..m}$ 就是 $T$ 由第 $i$ 个字母算起的后缀)。
Comet OJ