Problem Description

Given $n$ strings consisting of lowercase letters, define the value of the $i$-th string as the number of its meaningful substrings (if there are multiple essentially identical substrings, they are also counted multiple times). A substring of the $i$-th string is meaningful if and only if it can be split into several strings, where each part is a suffix of any of the $n$ strings.

Here is an example with $n=4$:

int
printf
scanf
ntnt

• For the string printf, the substring intf is meaningful, because it can be represented as int and f, which are suffixes of int and scanf, respectively. However, rint is not.

• For the string ntnt, the substring ntnt is also meaningful, because it can be represented as nt and nt (both are the same suffix of int), or it can be represented as ntnt, which is a suffix of ntnt.

Now, Little Z wants to know the sum of the values of these $n$ strings.

Input Format

The first line contains an integer $n$.

Then follow $n$ lines, each containing a string.

Output Format

Output one integer in one line, representing the sum of the values.

4
int
printf
scanf
ntnt

23

4
ireallywanttobemissjiaransdog
butmissjiaransaidthatshelikedcatsandicried
iknowwhyicrywheniamneitheradognoracatbecauseimactuallyamouse
ineverexpectedmissjiarantolikeherselfiunderstandthatallpeopleliketounderstandthecutedogorcatthatyuyuusestomakemoneyandnoonelikesthemousewithwetandwetdiseases

391

Hint

Constraints

This problem uses bundled testdata and O2 optimization.

Let $s_i$ denote the length of the $i$-th string.

For $100\%$ of the testdata, $1\le n \le 5\times10^5$, and $n\le \sum\limits \lvert s_i \rvert \le 10^6$.

Translated by ChatGPT 5