CF1902E.Collapsing Strings

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)|$.

给你 $n$ 个字符串 $s_1, s_2, \dots, s_n$，均由小写拉丁字母组成。记 $|x|$ 表示字符串 $x$ 的长度。

定义两个字符串 $a$ 和 $b$ 的坍缩（collapse）操作 $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|})$，其中 $s_{l,r}$ 表示字符串 $s$ 从第 $l$ 个字母到第 $r$ 个字母的子串；
• 否则，$C(a, b) = a + b$，即两个字符串的拼接。

请计算 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$。

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$.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。

接下来的 $n$ 行中，每行包含一个字符串 $s_i$（$1 \le |s_i| \le 10^6$），由小写拉丁字母组成。

所有字符串的总长度不超过 $10^6$。

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

输出一个整数——$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$。