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 Aminul on 8/7/2019.
 */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class E {
    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        final int maxn = (int)2e5 + 100;
        char[] text = in.next().toCharArray();
        int n = in.nextInt();
        AhoCorasick ac = new AhoCorasick(maxn, 26);
        char[] pat[] = new char[n][];
        for (int i = 0; i < n; i++) {
            pat[i] = in.next().toCharArray();
            ac.add(pat[i]);
        }
        ac.buildFail();
        ac.query(text);
        int a[] = ac.cnt;

        ac = new AhoCorasick(maxn, 26);
        for (int i = 0; i < n; i++) {
            ac.add(reverseArray(pat[i]));
        }
        ac.buildFail();
        ac.query(reverseArray(text));
        int b[] = ac.cnt;

        int tlen = text.length;
        for (int i = 0, j = tlen - 1; i < j; i++, j--) {
            int tmp = b[i];
            b[i] = b[j];
            b[j] = tmp;
        }
        
        long ans = 0;
        for (int i = 0; i < tlen - 1; i++) {
            ans += a[i] * (long) b[i + 1];
        }
        pw.println(ans);
        pw.close();
    }

    static char[] reverseArray(char a[]) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            char temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        return a;
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class AhoCorasick {
        int n, alphabet = 26, idx;
        int trie[][], f[], cnt[], level[], l, Q[], fail[][], endCount[];

        AhoCorasick(int N, int alphabet) {
            n = N;
            this.alphabet = alphabet;
            trie = new int[n][];
            f = new int[n];
            fail = new int[n][];
            cnt = new int[n];
            level = new int[n];
            Q = new int[n];
            endCount = new int[n];
            init();
        }

        void init() {
            trie[0] = new int[alphabet];
            fail[0] = new int[alphabet];
            f[0] = cnt[0] = endCount[0] = 0;
            idx = 1;
            l = 0;
        }

        int get_id(char ch) {
            return ch - 'a';
        }

        int add(char[] s) {
            int u = 0;
            for (char p : s) {
                int c = get_id(p);
                if (trie[u][c] == 0) {
                    trie[idx] = new int[alphabet];
                    fail[idx] = new int[alphabet];
                    f[idx] = cnt[idx] = endCount[idx] = 0;
                    trie[u][c] = idx++;
                }
                u = trie[u][c];
            }
            endCount[u]++;
            return u;
        }

        void buildFail() {
            f[0] = 0;
            fail[0][0] = 0;
            level[l++] = 0;
            int qe = 0, qs = 0;
            for (int c = 0; c < alphabet; ++c) {
                int u = trie[0][c];
                fail[0][c] = u;
                if (u != 0) {
                    f[u] = 0;
                    level[l++] = u;
                    Q[qe++] = u;
                }
            }
            while (qs < qe) {
                int r = Q[qs++];
                for (int c = 0; c < alphabet; ++c) {
                    int u = trie[r][c];
                    if (u != 0) {
                        Q[qe++] = u;
                        level[l++] = u;
                        f[u] = fail[f[r]][c];
                        fail[r][c] = trie[r][c];
                        endCount[u] += endCount[f[u]];
                    } else fail[r][c] = fail[f[r]][c];
                }
            }
        }

        int query(char[] s) {
            int matches = 0;
            int j = 0;
            int len = s.length;
            for (int i = 0; i < len; i++) {
                int c = get_id(s[i]);
                j = fail[j][c];
                cnt[i] += endCount[j];
            }
            return matches;
        }

        void finish() {
            for (int k = l - 1; k >= 0; k--) {
                int i = level[k];
                cnt[f[i]] += cnt[i];
            }
        }
    }


    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }


        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)) {
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}