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 AhoCorasick
    {
        int root=0, size=1;
        private ArrayList<Node> trie;
        private class Node
        {
            int next[], parent, wordID, link, nextWord, count, totalCount;
            char pch;
            boolean isLeaf;

            Node()
            {
                next=new int[ALPHA];Arrays.fill(next,-1);
                isLeaf=false; wordID=nextWord=link=parent=-1; totalCount=count=0;pch='\0';
            }
        }
        AhoCorasick()
        {
            trie =new ArrayList<>();
            trie.add(new Node());
        }
        void insert(int idx, 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]= size;
                    trie.add(new Node());

                    trie.get(size).parent=v;
                    trie.get(size).pch=ch;
                    size++;
                }
                v=trie.get(v).next[c];
            }
            trie.get(v).isLeaf=true;
            trie.get(v).wordID=idx;
            trie.get(v).count++;
            trie.get(v).totalCount++;
        }
        void clear(){trie.clear(); trie.add(new Node()); size=1;}
        void calcLink(int v)
        {
            if(v==root||trie.get(v).parent==root){trie.get(v).link=trie.get(v).nextWord=root; return;}

            int nextBetter=trie.get(trie.get(v).parent).link, link=root;
            int c=trie.get(v).pch-'a';

            while (true)
            {
                if(trie.get(nextBetter).next[c]!=-1){link=trie.get(nextBetter).next[c]; break;}
                if(nextBetter==root) break;
                nextBetter=trie.get(nextBetter).link;
            }

            trie.get(v).link=link;
            if(trie.get(link).isLeaf) trie.get(v).nextWord=link;
            else trie.get(v).nextWord=trie.get(link).nextWord;
            trie.get(v).totalCount+=trie.get(link).totalCount;
        }
        void build()
        {
            ArrayDeque<Integer> Q=new ArrayDeque<>();
            Q.add(root);

            while (!Q.isEmpty())
            {
                int v=Q.poll();
                calcLink(v);

                for(int i=0;i<ALPHA;i++)
                {
                    if(trie.get(v).next[i]==-1) continue;
                    Q.add(trie.get(v).next[i]);
                }
            }
        }
        void find(char text[], int store[])
        {
            int v=root, k=0;

            for(char ch:text)
            {
                int c=ch-'a';
                while (true)
                {
                    if(trie.get(v).next[c]!=-1) {v=trie.get(v).next[c];break;}
                    if(v==root) break;
                    v=trie.get(v).link;
                }

                int current=(trie.get(v).isLeaf)?v:trie.get(v).nextWord;
                while (current!=root) //don't include if indices aren't required
                {
                    store[k]+=trie.get(current).count;
                    current=trie.get(current).nextWord;
                }
                k++;
            }
        }
    }
    private static void reverse(int a[])
    {
        for(int i=0;i<a.length/2;i++)
        {
            int tmp=a[i];
            a[i]=a[a.length-i-1];
            a[a.length-i-1]=tmp;
        }
    }
    private static void reverse(char a[])
    {
        for(int i=0;i<a.length/2;i++)
        {
            char tmp=a[i];
            a[i]=a[a.length-i-1];
            a[a.length-i-1]=tmp;
        }
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N,M;

        AhoCorasick aho=new AhoCorasick();
        AhoCorasick revAho=new AhoCorasick();

        char text[]=br.readLine().trim().toCharArray();
        char revText[]=Arrays.copyOf(text,text.length);
        reverse(revText);

        N=Integer.parseInt(br.readLine().trim());
        M=text.length;

        for(i=0;i<N;i++)
        {
            char pattern[]=br.readLine().trim().toCharArray();
            char revPattern[]=Arrays.copyOf(pattern,pattern.length);
            reverse(revPattern);

            aho.insert(i,pattern);
            revAho.insert(i,revPattern);
        }

        aho.build();
        revAho.build();

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

        aho.find(text,end);
        revAho.find(revText,start);
        reverse(start);

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

        System.out.println(count);
    }
}