You Are Given Some Strings...

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给你一个字符串 $t$ 和 $n$ 个字符串 $s_1,s_2,\cdots,s_n$。所有字符串均由小写英文字母组成。

令 $f(t,s)$ 表示字符串 $s$ 作为子串在 $t$ 中的出现次数。例如，$f(\text{aaabacaa},\text{aa})=3$，$f(\text{ababa},\text{aba})=2$。

计算 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n f(t,s_i+s_j)$。$s_i+s_j$ 表示 $s_j$ 拼接在 $s_i$ 之后形成的字符串。

输入格式

第一行一个字符串 $t(1\le \vert t\vert\le 2\times 10^5)$。
第二行一个整数 $n(1\le n\le 2\times 10^5)$。
接下来 $n$ 行，每行一个字符串 $s_i(1\le \vert s_i\vert \le 2\times 10^5)$。

保证 $\sum\limits_{i=1}^n \vert s_i\vert\le 2\times 10^5$。

输出格式

输出一行一个整数表示答案。

样例输入 1

aaabacaa
2
a
aa

样例输出 1

5

样例输入 2

aaabacaa
4
a
a
a
b

样例输出 2

33

数据范围

• $1\le |t|\le 2\times 10^5$。
• $1\le n\le 2\times 10^5$。
• $1\le |s_i|\le 2\times 10^5$。
• $\sum_{i=1}^n |s_i|\le 2\times 10^5$。
• 所有字符串只含小写英文字母。