Problem: You are given a string t and n strings s_1, s_2, ..., 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('aaabacaa', 'aa') = 3, and f('ababa', 'aba') = 2.

Calculate the value of ∑_{i=1}^{n} ∑_{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 ≤ |t| ≤ 2 ⋅ 10^5).

The second line contains integer n (1 ≤ n ≤ 2 ⋅ 10^5).

Each of next n lines contains string s_i (1 ≤ |s_i| ≤ 2 ⋅ 10^5).

It is guaranteed that ∑_{i=1}^{n} |s_i| ≤ 2 ⋅ 10^5. All strings consist of lowercase English letters.

Output

Print one integer — the value of ∑_{i=1}^{n} ∑_{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

Solution (in PYTHON):

Solution:
from __future__ import division, print_function

from collections import deque
class Node:
    def __init__(self, c, nxt, fail, o):
        self.c = c
        self.nxt = nxt
        self.fail = fail
        self.o = o

root = Node('', {}, Node, 0)
root.fail = root

def new_node(par, c):
    node = Node(c, {}, root, 0)
    par.nxt[c] = node
    return node

def go(n, c):
    while True:
        try:
            return n.nxt[c]
        except KeyError:
            if n != root:
                n = n.fail
            else:
                return root

def build(ps):
    for i, p in enumerate(ps):
        n = root
        for c in p:
            try:
                n = n.nxt[c]
            except KeyError:
                n = new_node(n, c)
        n.o += 1

    q = deque([root])
    while q:
        n = q.popleft()
        for c, cn in n.nxt.iteritems():
            q.append(cn)
            if n == root:
                cn.fail = root
            else:
                cn.fail = go(n.fail, c)
            cn.o += cn.fail.o

def query(s, ar):
    n = root
    for i, c in enumerate(s):
        n = go(n, c)
        ar[i] += n.o

def main():
    s = input()
    ps = [input() for _ in range(int(input()))]

    build(ps)
    far = array_of(int, len(s))
    query(s, far)

    root.nxt = {}
    root.o = 0

    rps = [list(reversed(ss)) for ss in ps]
    rs = list(reversed(s))

    build(rps)
    bar = array_of(int, len(rs))
    query(rs, bar)

    ans = 0
    for i in range(len(s)-1):
        ans += bar[i] * far[len(s)-2-i]
    print(ans)
 
INF = float('inf')
MOD = 10**9 + 7
 
import os, sys
from atexit import register
from io import BytesIO
import itertools
 
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange
 
    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip
 
if 0:
    debug_print = print
else:
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
    sys.stdout = BytesIO()
    register(lambda: os.write(1, sys.stdout.getvalue()))
 
    input = lambda: sys.stdin.readline().rstrip('\r\n')
    debug_print = lambda *x, **y: None
 
 
def input_as_list():
    return list(map(int, input().split()))
 
def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()
 
main()