「SvR-2」Work

给定 $n$ 个**由小写字母组成**的字符串，定义第 $i$ 个字符串的价值为其有意义的子串的数量（**如果有多个本质相同的子串也统计多次**），第 $i$ 个字符串的一个子串有意义，当且仅当这个子串能被分成若干个串，其中每个串都是这 $n$ 个字符串中任意一个字符串的任意一个后缀。 这里有一个 $n=4$ 的例子： ```plain 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$。