String Distance

对于字符串 $a,b$，你可以进行下列操作： - 选择其中任意一个字符串的子串，并将其从小到大排序。 我们定义 $f(a,b)$ 为字符串 $a,b$ 进行上述操作使 $a=b$ 所需的最小次数，特别的，如果无论如何都不可能使 $a=b$，$f(a,b)=1337$。例如： - $f(\texttt{"ab"},\texttt{"ab"})=0$，因为这两个字符串本身就已经相同。 - $f(\texttt{"ba"},\texttt{"ab"})=1$，你可以将整个第一个字符串排序。 - $f(\texttt{"ebcda"},\texttt{"ecbda"})=1$，你可以选择第二个字符串的第二个到第四个字符排序。 - $f(\texttt{"a"},\texttt{"b"})=1337$，显然无法通过上述操作使这两个字符串相同。 给定 $n$ 个长度相等的字符串 $s_1,s_2,\cdots,s_n$，所有这些字符串都是两两不同的。 求 $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nf(s_i,s_j)$。 $1\leq n\leq2\times10^5;|s_1|=|s_2|=\cdots=|s_n|;\sum|s_i|\leq2\times10^5;$

Suppose you are given two strings $ a $ and $ b $ . You can apply the following operation any number of times: choose any contiguous substring of $ a $ or $ b $ , and sort the characters in it in non-descending order. Let $ f(a, b) $ the minimum number of operations you have to apply in order to make them equal (or $ f(a, b) = 1337 $ if it is impossible to make $ a $ and $ b $ equal using these operations). For example: - $ f(\text{ab}, \text{ab}) = 0 $ ; - $ f(\text{ba}, \text{ab}) = 1 $ (in one operation, we can sort the whole first string); - $ f(\text{ebcda}, \text{ecdba}) = 1 $ (in one operation, we can sort the substring of the second string starting from the $ 2 $ -nd character and ending with the $ 4 $ -th character); - $ f(\text{a}, \text{b}) = 1337 $ . You are given $ n $ strings $ s_1, s_2, \dots, s_k $ having equal length. Calculate $ \sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j) $ .

The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of strings. Then $ n $ lines follow, each line contains one of the strings $ s_i $ , consisting of lowercase Latin letters. $ |s_1| = |s_2| = \ldots = |s_n| $ , and $ n \cdot |s_1| \le 2 \cdot 10^5 $ . All these strings are pairwise distinct.

Print one integer: $ \sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j) $ .

4
zzz
bac
abc
acb

4015

2
a
b

1337