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

样例输入 #1

aaabacaa
2
a
aa

样例输出 #1

5

样例 #2

样例输入 #2

aaabacaa
4
a
a
a
b

样例输出 #2

33