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

Solution:
//created by Whiplash99
import java.io.*;
import java.util.*;
public class E
{
    private static final int ALPHA=26;
    static class Trie
    {
        int root=0;
        private ArrayList<Node> trie;
        private class Node
        {
            int next[], count;
            boolean isLeaf;

            Node()
            {
                next=new int[ALPHA];Arrays.fill(next,-1);
                isLeaf=false; count=0;
            }
        }
        Trie()
        {
            trie =new ArrayList<>();
            trie.add(new Node());
        }
        void insert(char str[])
        {
            int v=root;
            for(char ch:str)
            {
                int c=ch-'a';
                if(trie.get(v).next[c]==-1)
                {
                    trie.get(v).next[c]= trie.size();
                    trie.add(new Node());
                }
                v=trie.get(v).next[c];
            }
            trie.get(v).isLeaf=true;
            trie.get(v).count++;
        }
        int countPrefixes(char str[], int pos)
        {
            int v=root, ans=0;
            for(int i=pos;i<str.length;i++)
            {
                int c=str[i]-'a';
                if(trie.get(v).next[c]==-1)break;
                v=trie.get(v).next[c];
                ans+=trie.get(v).count;
            }
            return ans;
        }
        void clear(){trie.clear(); trie.add(new Node());}
    }
    public static void countMatches1(char text[], char pat[], int store[])
    {
        String s=new String(pat)+"$"+new String(text);
        int M=text.length, N=pat.length, count=0;
        int[] pi=new int[M+N+1];
        calcPi(s.toCharArray(),pi,M+N+1);

        for(int i=N+1;i<M+N+1;i++) if(pi[i]==N) store[i-2*N]++;
    }
    private static void calcPi(char str[], int pi[], int N)
    {
        for (int i = 1, j=0; i < N; i++)
        {
            while (j > 0 && str[i] != str[j]) j = pi[j-1];
            if (str[i] == str[j]) j++;
            pi[i] = j;
        }
    }
    public static void reverse(int a[])
    {
        for(int i=0,j=a.length-1;i<a.length/2;i++,j--) {int tmp=a[i];a[i]=a[j];a[j]=tmp;}
    }
    public static char[] reverse(char a[])
    {
        char ans[]=new char[a.length];
        for(int i=0,j=a.length-1;i<a.length;i++,j--) ans[i]=a[j];
        return ans;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;

        char text[]=br.readLine().trim().toCharArray();
        char revText[]=reverse(text);

        N=Integer.parseInt(br.readLine().trim());
        int M=text.length;
        int SQRT=(int)Math.sqrt(M)+1;

        int start[]=new int[M];
        int end[]=new int[M];

        Trie trie=new Trie();
        Trie revTrie=new Trie();

        for(i=0;i<N;i++)
        {
            char pat[]=br.readLine().trim().toCharArray();
            char revPat[]=reverse(pat);

            if(pat.length<=SQRT)
            {
                trie.insert(pat);
                revTrie.insert(revPat);
            }
            else
            {
                countMatches1(text,pat,start);
                countMatches1(revText,revPat,end);
            }
        }

        for(i=0;i<M;i++)
        {
            start[i]+=trie.countPrefixes(text,i);
            end[i]+=revTrie.countPrefixes(revText,i);
        }

        reverse(end);
        long ans=0;
        for(i=1;i<M;i++) ans+=(long) end[i-1]*start[i];

        System.out.println(ans);
    }
}