Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

E. You Are Given Some Strings...
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Examples
Input
aaabacaa
2
a
aa

Output
5

Input
aaabacaa
4
a
a
a
b

Output
33