给你 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_n$$$,由小写拉丁字母组成。令 $$$|x|$$$ 为字符串 $$$x$$$ 的长度。
设两个字符串 $$$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|})$$$,其中 $$$s_{l,r}$$$ 是 $$$s$$$ 从第 $$$l$$$ 到第一个字母的子串第 $$$r$$$ 个;
- 否则,$$$C(a, b) = a + b$$$, i. e.两个字符串的串联。
计算 $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。
接下来的 $$$n$$$ 行包含一个字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 10^6$$$),由小写拉丁字母组成。
字符串的总长度不超过$$$10^6$$$。
输出
打印单个整数 — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$。
示例
输入 #1
3 aba ab ba
输出 #1
20
输入 #2
5 abab babx xab xba bab
输出 #2
126