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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author svilen.marchev@gmail.com
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    String t;
    ArrayList<String> s = new ArrayList<>();
    int m;
    int[] numStartingAt;
    int[] numEndingAt;

    void matchWithKmp(String s) {
      int[] prefix = StringUtils.prefixFunction(s);
      int q = 0;
      for (int i = 0; i < t.length(); ++i) {
        while (q > 0 && t.charAt(i) != s.charAt(q)) {
          q = prefix[q - 1];
        }
        if (t.charAt(i) == s.charAt(q)) {
          ++q;
        }
        if (q == s.length()) {
          int startIx = i - s.length() + 1;
//        System.out.println("KMP: Match of " + s + " starting at " + startIx + " ending at " + i);
          q = prefix[q - 1];

          numStartingAt[startIx]++;
          numEndingAt[i]++;
        }
      }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      t = in.readString();
      int n = in.readInt();
      int totalLen = 0;
      for (int i = 0; i < n; ++i) {
        String tmp = in.readString();
        s.add(tmp);
        totalLen += tmp.length();
      }

      numEndingAt = new int[t.length()];
      numStartingAt = new int[t.length()];
      m = (int) Math.sqrt(totalLen) + 1;

      // Part 1: for long si strings, s.t. |si|>=m
      //
      // Use KMP and the prefix function.
      for (int i = 0; i < n; ++i) {
        if (s.get(i).length() >= m) {
          matchWithKmp(s.get(i));
        }
      }

      // Part 2: for short si stings, s.t. |si|<m
      //
      // Use a trie to add all small strings, and then for each position of t, walk down the trie
      // and update numStartingAt and numEndingAt whenever some of the trie nodes are end of some
      // strings from si.
      SvTrie trie = new SvTrie();
      for (int i = 0; i < n; ++i) {
        if (s.get(i).length() < m) {
          trie.add(s.get(i));
        }
      }
      for (int i = 0; i < t.length(); ++i) {
        SvTrie.TrieNode cur = trie.getRoot();
        for (int q = 0; q < m - 1 && i + q < t.length(); ++q) {
          cur = cur.getLink(t.charAt(i + q));
          if (cur == null) {
            break;
          }

//        System.out.println("Trie: Match starting at " + i + " ending at " + (i + q));
          numStartingAt[i] += cur.getTerminatingStringsCount();
          numEndingAt[i + q] += cur.getTerminatingStringsCount();
        }
      }

      long ans = 0;
      for (int i = 0; i < t.length() - 1; ++i) {
        ans += (long) numEndingAt[i] * numStartingAt[i + 1];
      }
      out.println(ans);
    }

  }

  static class SvTrie {
    private SvTrie.TrieNode root = new SvTrie.TrieNode();

    public SvTrie() {
    }

    public void add(String s) {
      SvTrie.TrieNode cur = root;
      for (int i = 0; i < s.length(); ++i) {
        if (cur.links[s.charAt(i)] == null) {
          cur.links[s.charAt(i)] = new SvTrie.TrieNode();
        }
        cur = cur.links[s.charAt(i)];
      }
      cur.value++;
    }

    public SvTrie.TrieNode getRoot() {
      return root;
    }

    public static class TrieNode {
      private SvTrie.TrieNode[] links = new SvTrie.TrieNode[128];
      private int value = 0;

      public SvTrie.TrieNode getLink(int next) {
        return links[next];
      }

      public int getTerminatingStringsCount() {
        return value;
      }

    }

  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public String readString() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      StringBuilder res = new StringBuilder();
      do {
        if (Character.isValidCodePoint(c)) {
          res.appendCodePoint(c);
        }
        c = read();
      } while (!isSpaceChar(c));
      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);

    }

  }

  static class StringUtils {
    public static int[] prefixFunction(CharSequence s) {
      int l = s.length();
      int[] p = new int[l];
      int k = 0;
      for (int i = 1; i < l; i++) {
        while ((k > 0) && (s.charAt(k) != s.charAt(i))) {
          k = p[k - 1];
        }
        if (s.charAt(k) == s.charAt(i)) {
          k++;
        }
        p[i] = k;
      }
      return p;
    }

  }
}