CF1902E Collapsing Strings

You are given $ n $ strings $ s_1, s_2, \dots, s_n $ , consisting of lowercase Latin letters. Let $ |x| $ be the length of string $ x $ . Let a collapse $ C(a, b) $ of two strings $ a $ and $ b $ be the following operation: - if $ a $ is empty, $ C(a, b) = b $ ; - if $ b $ is empty, $ C(a, b) = a $ ; - if the last letter of $ a $ is equal to the first letter of $ b $ , then $ C(a, b) = C(a_{1,|a|-1}, b_{2,|b|}) $ , where $ s_{l,r} $ is the substring of $ s $ from the $ l $ -th letter to the $ r $ -th one; - otherwise, $ C(a, b) = a + b $ , i. e. the concatenation of two strings. Calculate $ \sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)| $ .

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ). Each of the next $ n $ lines contains a string $ s_i $ ( $ 1 \le |s_i| \le 10^6 $ ), consisting of lowercase Latin letters. The total length of the strings doesn't exceed $ 10^6 $ .

Print a single integer — $ \sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)| $ .