310870: CF1902E. Collapsing Strings

E. Collapsing Stringstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given $n$ strings $s_1, s_2, \dots, s_n$, consisting of lowercase Latin letters. Let $|x|$ be the length of string $x$.

Let a collapse $C(a, b)$ of two strings $a$ and $b$ be the following operation:

• if $a$ is empty, $C(a, b) = b$;
• if $b$ is empty, $C(a, b) = a$;
• if the last letter of $a$ is equal to the first letter of $b$, then $C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$, where $s_{l,r}$ is the substring of $s$ from the $l$-th letter to the $r$-th one;
• otherwise, $C(a, b) = a + b$, i. e. the concatenation of two strings.

Calculate $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^6$).

Each of the next $n$ lines contains a string $s_i$ ($1 \le |s_i| \le 10^6$), consisting of lowercase Latin letters.

The total length of the strings doesn't exceed $10^6$.

Output

Print a single integer — $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$.

ExamplesInput

3
aba
ab
ba

Output

20

Input

5
abab
babx
xab
xba
bab

Output

126

题目大意：
这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下：
- 如果a为空，则C(a, b) = b；
- 如果b为空，则C(a, b) = a；
- 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串；
- 否则，C(a, b) = a + b，即两个字符串的连接。

计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。

输入输出数据格式：
输入：
- 第一行包含一个整数n（1 ≤ n ≤ 10^6）。
- 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。
- 字符串的总长度不超过10^6。

输出：
- 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。

示例：
输入：
3
aba
ab
ba

输出：
20

输入：
5
abab
babx
xab
xba
bab

输出：
126题目大意： 这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下： - 如果a为空，则C(a, b) = b； - 如果b为空，则C(a, b) = a； - 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串； - 否则，C(a, b) = a + b，即两个字符串的连接。 计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。 输入输出数据格式： 输入： - 第一行包含一个整数n（1 ≤ n ≤ 10^6）。 - 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。 - 字符串的总长度不超过10^6。 输出： - 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。 示例： 输入： 3 aba ab ba 输出： 20 输入： 5 abab babx xab xba bab 输出： 126