有 $n\times m$ 个由小写字母组成的字符串 $s_{i,j}(1\le i\le n,1\le j\le m)$。

你需要求出：

$$\sum_{i=1}^{n}\sum_{j=1}^n\max_{k=1}^m\operatorname{LCP}(s_{i,k},s_{j,k})$$

的值。

$1\le n\le10^6,1\le m\le 3$，令 $S=\sum|s_{i,j}|$，$ S\le3\times10^6$

example

input1:

3 2
aa ab
ab ab
a a

output1:

13

input2:

6 3
acb aca bba
aba bab bca
bdc caa dda
cab bdb bca
aac bab cdd
aab bab cda

output2:

54

data

对于 $15\%$ 的数据，有 $n\le100,S\le300$。

对于 $30\%$ 的数据，有 $n\le3000$。

对于另外 $10\%$ 的数据，有 $m=1$。

对于另外 $20\%$ 的数据，有 $m=2$。

对于另外 $20\%$ 的数据，有 $S\le 3\times 10^5$。

对于 $100\%$ 的数据，有 $1\le n\le10^6,1\le m\le 3, S\le3\times10^6$。