Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

string suffix structures

strings

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. You Are Given Some Strings...

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 13:41:10 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|