Description:
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 Format:
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 Format:
Print a single integer — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.
Note:
None