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:
import java.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {
    static String pp[];
    static String s;
    static long prefix[], suffix[];
    static int n;
    static void solve(long res[])
    {
        SAM1 sam=new SAM1();
        sam.init(410000,26);
        for(int i=0;i<s.length();++i)
        sam.insert(s.charAt(i) - 'a');
        sam.topo();
        SAM_node k = sam.root;
        for (int i = 1; i <= n; ++i)
        {
            k = sam.root;
            for (int j=0;j<pp[i].length();++j)
            if (k!=null)
                k = k.next[pp[i].charAt(j) - 'a'];
            if (k!=null)
                k.times++;
            StringBuilder sp=new StringBuilder(pp[i]);
            sp.reverse();
            pp[i]=sp.toString();
        }
        int cnt = sam.cur;
        for (int i = 1; i < cnt; ++i)
            sam.pool[i].times += sam.pool[i].pre.times;
        k = sam.root;
        for (int i = 0; i < s.length(); ++i)
        {
            k = k.next[s.charAt(i) - 'a'];
            res[i + 1] = k.times;
        }
    }
    public static InputReader in = new InputReader(System.in);
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)
    {
        prefix=new long[210000];
        suffix=new long[210000];
        long suffix2[]=new long[210000];
        Arrays.fill(suffix2,0);
        Arrays.fill(prefix,0);
        Arrays.fill(suffix,0);
        pp=new String[210000];
        s=in.next();
        n=in.nextInt();
        for(int i=1;i<=n;++i)
            pp[i]=in.next();
        solve(prefix);
        StringBuilder sp=new StringBuilder(s);
        sp.reverse();
        s=sp.toString();
        solve(suffix);

        for (int i = 1; i <= s.length(); ++i)
            suffix2[i]=suffix[s.length()-i+1];
        long ans = 0;
        for (int i = 1; i < s.length(); ++i)
            ans += prefix[i] * suffix2[i + 1];
        out.println(ans);
        out.flush();
        out.close();
    }
}
class SAM_node
{
    SAM_node pre,next[];
    int step;
    long times;
    SAM_node(int sigma)
    {
        times=0;
        next=new SAM_node[sigma];
        step=0;
        pre=null;
    }
}
class SAM1
{
    SAM_node SAM_pool[],root,last;
    int d[];
    SAM_node pool[];
    int cur;
    int sigma;
    void topo() {
        // 求出parent树的拓扑序
        int cnt = cur;
        int maxVal = 0;
        Arrays.fill(d, 0);
        for (int i = 1; i < cnt; i++) {
            maxVal = Math.max(maxVal, SAM_pool[i].step);
            d[SAM_pool[i].step]++;
        }
        for (int i = 1; i <= maxVal; i++)
            d[i] += d[i - 1];
        for (int i = 1; i < cnt; i++)
            pool[d[SAM_pool[i].step]--] = SAM_pool[i];
        pool[0] = root;
    }
    void init(int a,int b)
    {
        d=new int[a];
        pool=new SAM_node[a];
        SAM_pool=new SAM_node[a];
        SAM_pool[0]=new SAM_node(b);
        sigma=b;
        root=last=SAM_pool[0];
        cur=1;
    }
    void insert(int w)
    {
        SAM_node p=last;
        SAM_pool[cur]=new SAM_node(sigma);
        SAM_node np=SAM_pool[cur];
        last=np;
        cur++;
        np.step=p.step+1;
        while (p!=null && p.next[w]==null)
        {
            p.next[w]=np;
            p = p.pre;
        }
        if(p==null)
        {
            np.pre=root;
        }
        else
        {
            SAM_node q=p.next[w];
            if(p.step+1==q.step)
                np.pre=q;
            else {
                SAM_node nq = SAM_pool[cur++] = new SAM_node(sigma);
                nq.next = Arrays.copyOf(q.next, sigma);
                nq.step = p.step + 1;
                nq.pre = q.pre;
                q.pre = nq;
                np.pre = nq;
                while (p != null && p.next[w]==(q)) {
                    p.next[w] = nq;
                    p = p.pre;
                }
            }
        }
    }
}
class InputReader{
    private final static int BUF_SZ = 65536;
    BufferedReader in;
    StringTokenizer tokenizer;
    public InputReader(InputStream in) {
        super();
        this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
        tokenizer = new StringTokenizer("");
    }
    public boolean hasNext() {  //处理EOF
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                String line = in.readLine();
                if(line == null) return false;
                tokenizer = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
    public String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong()
    {
        return Long.parseLong(next());
    }
}