You Are Given Some Strings...

题意翻译

你有一个字符串$t$和$n$个字符串$s_1,s_2,...,s_n$,所有字符串都只含有小写英文字母。 令$f(t,s)$为$s$在$t$中的出现次数，如$f('aaabacaa','aa')=3$,$f('ababa','aba')=2$. 请计算$\sum_{i=1}^n\sum_{j=1}^nf(t,s_i+s_j)$,其中$s+t$代表$s$和$t$连接起来。 注意如果存在两对整数$i_1,j_1,i_2,j_2$,使$s_{i_1}+s_{j_1}=s_{i_2}+s_{j_2}$,你需要把$f(t,s_{i_1}+s_{j_1})$和$f(t,s_{i_2}+s_{j_2})$在答案里。

题目描述

You 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.

输入输出格式

输入格式

The 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.

输出格式

Print one integer — the value of $ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j) $ .

输入输出样例

输入样例 #1

aaabacaa
2
a
aa

输出样例 #1

5

输入样例 #2

aaabacaa
4
a
a
a
b

输出样例 #2

33