Tổng độ tương đồng tiền tố

Bối cảnh và bài toán

Một hệ thống phân nhóm từ khóa đánh giá độ gần nhau của hai từ bằng số ký tự đầu liên tiếp giống nhau. Để ước lượng độ "tụ cụm" của toàn bộ kho từ khóa, cần tính tổng độ dài tiền tố chung dài nhất trên mọi cặp khác nhau.

Yêu cầu

Tính sum LCP(S_i, S_j) trên mọi cặp 1 <= i < j <= N.

Input

Dòng đầu chứa N, sau đó N dòng là các chuỗi.

Output

In một số nguyên 64-bit là tổng cần tìm.

Ràng buộc

• 2 <= N <= 3 * 10^5
• Tổng độ dài các chuỗi không vượt 3 * 10^5.
• Chuỗi chỉ gồm chữ cái thường a..z.

Chấm điểm

Ví dụ 1

Input

3
ab
abc
arc

Output

4

Giải thích. LCP lần lượt là 2, 1, 1 nên tổng bằng 4.

Ví dụ 2

Input

4
a
aa
aaa
b

Output

4

Giải thích. Ba cặp trong nhánh a có LCP 1,1,2; các cặp với b có LCP 0.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: AtCoder Beginner Contest 353 – E – Yet Another Sigma Problem.