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 PYTHON3):

Solution:
class Node(object):
    def __init__(self):
        super(Node, self).__init__()
        self.next = [-1] * 26
        self.trans = []
        self.matches = 0
        self.leaf = 0
        self.link = 0

class AhoCorasick(object):
    def __init__(self):
        super(AhoCorasick, self).__init__()
        self.T = [Node()]
        self.T[0].link = 0

    def insert_trie(self, s):
        v = 0
        for i in range(len(s)):
            c = ord(s[i]) - ord('a')
            if(self.T[v].next[c] == -1):
                self.T[v].trans.append(c)
                self.T[v].next[c] = len(self.T)
                self.T.append(Node())
            v = self.T[v].next[c]
        self.T[v].leaf += 1
        self.T[v].matches += 1

    def set_suffix_link(self, S):
        Q = []
        for j in range(len(S)):
            Q.append((j, 0, 0, 0))
            #string index, index in string, state, suff state, 
        i = 0
        while(i < len(Q)):
            j,ind,v,suff = Q[i]
            i += 1
            c = ord(S[j][ind]) - ord('a')
            if(ind>0):
                while(suff>0 and self.T[suff].next[c]==-1):
                    suff = self.T[suff].link
                if(self.T[suff].next[c] != -1):
                    suff = self.T[suff].next[c]
            v = self.T[v].next[c]
            self.T[v].link = suff
            if(ind+1 < len(S[j])):
                Q.append((j,ind+1,v,suff))

    def set_matches(self):
        i = 0
        Q = [0]
        while(i < len(Q)):
            v = Q[i]
            self.T[v].matches = self.T[v].leaf + self.T[self.T[v].link].matches
            for c in self.T[v].trans:
                Q.append(self.T[v].next[c])
            i += 1

    def build(self, S):
        for i in range(len(S)):
            self.insert_trie(S[i])
        self.set_suffix_link(S)
        #self.printTree()
        self.set_matches()

    def get(self, s):
        v = 0
        matches = []
        for i in range(len(s)):
            c = ord(s[i]) - ord('a')
            while(v>0 and self.T[v].next[c] == -1):
                v = self.T[v].link
            if(self.T[v].next[c] != -1):
                v = self.T[v].next[c]
            matches.append(self.T[v].matches)
        return matches

    def printTree(self):
        for i in range(len(self.T)):
            print(str(i)+" leaf:"+str(self.T[i].leaf)+" link:"+str(self.T[i].link)+" matches:"+str(self.T[i].matches)+" : " , end='')
            for j in range(26):
                print(" "+str(chr(j+ord('a')))+"-"+(str(self.T[i].next[j]) if (self.T[i].next[j]!=-1) else "_")+" ", end='')
            print()

t = input()
n = int(input())
patterns = []
patterns_rev = []
for i in range(n):
    s = input()
    patterns.append(s)
    patterns_rev.append(s[::-1])
t1 = AhoCorasick()
t2 = AhoCorasick()
t1.build(patterns)
t2.build(patterns_rev)

x1 = t1.get(t)
x2 = t2.get(t[::-1])[::-1]

#print(x1)
#print(x2)

ans = 0
for i in range(len(x1)-1):
    ans += x1[i] * x2[i+1]

print(ans)