Sum of LCPs · CODER HUSC

Với hai xâu $x$ ~x~ và $y$ ~y~, hàm $f(x,y)$ ~f(x,y)~ được định nghĩa là độ dài của tiền tố chung dài nhất của hai xâu $x$ ~x~ và $y$ ~y~.

Cho $n$ ~n~ xâu $s_1,s_2,..,s_n$ ~s_1,s_2,..,s_n~ chỉ chứa các ký tự chữ cái in thường, bạn hãy tính giá trị biểu thức:

$\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(s_i,s_j)$

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(2 \le n \le 3 \times 10^5)$ ~(2 \le n \le 3 \times 10^5)~.
Dòng thứ hai chứa $n$ ~n~ xâu $s_1,s_2,...,s_n$ ~s_1,s_2,...,s_n~ chỉ chứa các ký tự chữ cái in thường $(1 \le |s_i|$ ~(1 \le |s_i|~ $;$ ~;~ $|s_1|+|s_2|+...+|s_n| \le 3 \times 10^5)$ .