E. Collapsing Stringstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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)|.InputThe 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.OutputPrint a single integer — \sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|.ExamplesInput
3abaabbaOutput
20
Input
5ababbabxxabxbababOutput
126

3abaabba
20 
['data structures', 'strings', 'trees', '*1900']