假设给你两个字符串 $$$a$$$ 和 $$$b$$$。您可以多次应用以下操作:选择 $$$a$$$ 或 $$$b$$$ 的任何连续子字符串,并按非降序对其中的字符进行排序。让 $$$f(a, b)$$$ 为使它们相等而必须应用的最少操作数(或者 $$$f(a, b) = 1337$$$ 如果使用这些操作不可能使 $$$a$$$ 和 $$$b$$$ 相等)。
例如:
- $$$f(\text{ab}, \text{ab}) = 0$$$;
- $$$f(\text{ba}, \text{ab}) = 1$$$ (在一次操作中,我们可以对整个第一个字符串进行排序);
- $$$f(\text{ebcda}, \text{ecdba}) = 1$$$ (在一次操作中,我们可以对第二个字符串的子字符串进行排序,从第 $$$2$$$ 个字符开始,到第 $$$4$$$ 个字符结束);
- $$$f(\text{a}, \text{b}) = 1337$$$。
给你 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_k$$$ 具有相同的长度。计算 $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串的数量。
接下来是 $$$n$$$ 行,每一行包含字符串 $$$s_i$$$ 之一,由小写拉丁字母组成。 $$$|s_1| = |s_2| = \ldots = |s_n|$$$ 和 $$$n \cdot |s_1| \le 2 \cdot 10^5$$$。所有这些字符串都是成对不同的。
输出
打印一个整数:$$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$。
示例
输入 #1
4 zzz bac abc acb
输出 #1
4015
输入 #2
2 a b
输出 #2
1337