Zenyk and strings

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a set of \(n\) strings \(s_i\) and a string \(t\).

He became curious about how harmoniously the string \(t\) combines with the set.

Zenyk defines the harmony of the string \(t\) and the set \(s\) as \(\sum_{i = 1} ^{n} f(s_i, t)\), where \(f(s, t) = \sum_{i=1}^{|t|} |lcp(s, t_{i..|t|})|\), \(|t|\) is the length of the string \(t\), \(t_{i..|t|}\) is the suffix of the string \(t\) starting at position \(i\), \(lcp(s, t)\) is the longest common prefix of strings \(s\) and \(t\).

Help Zenyk calculate the harmony of his strings.

Input

The first line contains \(t\).

The second line contains an integer \(n\) — the number of strings in the set.

The next \(n\) lines contain \(s_i\).

Output

Print a single integer in one line — the answer to the problem.

Constraints

\(1 \le |t| \le 10^5\),

\(1 \le n \le 10^5\),

\(1 \le \sum_{i=1} ^n |s_i| \le 10^5\),

all strings consist of lowercase Latin letters.

Samples