E. You Are Given Some Strings...time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a string t and n strings s_1, s_2, \dots, s_n. All strings consist of lowercase Latin letters.Let f(t, s) be the number of occurences of string s in string t. For example, f('\text{aaabacaa}', '\text{aa}') = 3, and f('\text{ababa}', '\text{aba}') = 2.Calculate the value of \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j), where s + t is the concatenation of strings s and t. Note that if there are two pairs i_1, j_1 and i_2, j_2 such that s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}, you should include both f(t, s_{i_1} + s_{j_1}) and f(t, s_{i_2} + s_{j_2}) in answer.InputThe first line contains string t (1 \le |t| \le 2 \cdot 10^5).The second line contains integer n (1 \le n \le 2 \cdot 10^5).Each of next n lines contains string s_i (1 \le |s_i| \le 2 \cdot 10^5).It is guaranteed that \sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5. All strings consist of lowercase English letters.OutputPrint one integer — the value of \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j).ExamplesInput
aaabacaa
2
a
aa
Output
5
Input
aaabacaa
4
a
a
a
b
Output
33

aaabacaa
2
a
aa

5 
['brute force', 'string suffix structures', 'strings', '*2400']