题目描述

给定 $n$ 个由小写字母组成的字符串，定义第 $i$ 个字符串的价值为其有意义的子串的数量（如果有多个本质相同的子串也统计多次），第 $i$ 个字符串的一个子串有意义，当且仅当这个子串能被分成若干个串，其中每个串都是这 $n$ 个字符串中任意一个字符串的任意一个后缀。

这里有一个 $n=4$ 的例子：

int
printf
scanf
ntnt

• 对于 printf 这个字符串而言，intf 是有意义的，因为可以表示成 int 和 f ，分别是 int 和 scanf 的后缀，而 rint 则不是。

• 对于 ntnt 这个字符串而言，ntnt 也是有意义的，因为可以表示成 nt 和 nt，它们都是 int 同一个后缀，或者可以表示成 ntnt，是 ntnt 的一个后缀。

现在，小 Z 想知道这 $n$ 个字符串价值之和。

输入格式

第一行一个整数 $n$。

之后 $n$ 行，每行一个字符串。

输出格式

一行一个整数，表示价值之和。

4
int
printf
scanf
ntnt

23

4
ireallywanttobemissjiaransdog
butmissjiaransaidthatshelikedcatsandicried
iknowwhyicrywheniamneitheradognoracatbecauseimactuallyamouse
ineverexpectedmissjiarantolikeherselfiunderstandthatallpeopleliketounderstandthecutedogorcatthatyuyuusestomakemoneyandnoonelikesthemousewithwetandwetdiseases

391

提示

数据规模与约定

本题开启捆绑测试和 O2 优化。

令 $s_i$ 表示第 $i$ 个字符串长度。 | Subtask | 数据范围/特殊性质 | 分值 | | :------: | :------: | :------: | | $1$ | $n\le 3$，$\sum\limits \lvert s_i\rvert\le10$| $5 \operatorname{pts}$ | | $2$ | $n=26$，每种字符串均由一种字符组成 | $5 \operatorname{pts}$ | | $3$ |$n=1$ | $15 \operatorname{pts}$ | | $4$ | $\sum\limits \lvert s_i \rvert \le 2000$ | $15 \operatorname{pts}$ | | $5$ | $\sum\limits \lvert s_i \rvert \le 2\times10^5$ | $30 \operatorname{pts}$ | | $6$ | $\sum\limits \lvert s_i \rvert \le 10^6$ | $30 \operatorname{pts}$ |

对于 $100\%$ 的数据，$1\le n \le 5\times10^5$，$n\le \sum\limits \lvert s_i \rvert \le 10^6$。