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

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
const int MAX_N = 2e5 + 5;
struct SAM {
  int root, last, siz;
  int nxt[MAX_N << 1][26], fa[MAX_N << 1], ml[MAX_N << 1];
  int Right[MAX_N << 1], cnt[MAX_N << 1], id[MAX_N << 1];
  int pos[MAX_N << 1], ed[MAX_N << 1];
  void init() {
    root = last = siz = 1;
    ml[root] = fa[root] = Right[root] = 0;
    memset(nxt[root], 0, sizeof(nxt[root]));
  }
  void add(int c) {
    int p = last, np = ++siz;
    memset(nxt[np], 0, sizeof(nxt[np]));
    last = np, ml[np] = ml[p] + 1, Right[np] = 1;
    for (; p && !nxt[p][c]; p = fa[p]) nxt[p][c] = np;
    if (!p)
      fa[np] = root;
    else {
      int q = nxt[p][c];
      if (ml[p] + 1 == ml[q])
        fa[np] = q;
      else {
        int nq = ++siz;
        ml[nq] = ml[p] + 1, Right[nq] = 0;
        memcpy(nxt[nq], nxt[q], sizeof(nxt[q]));
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        for (; p && nxt[p][c] == q; p = fa[p]) nxt[p][c] = nq;
      }
    }
  }
  void build(char *s) {
    init();
    int len = strlen(s + 1);
    for (register int i = 1; i <= len; ++i) add(s[i] - 'a'), pos[i] = last;
  }
  void solve(char *s) {
    int now = root, len = strlen(s + 1);
    for (register int i = 1; i <= len; ++i) {
      if (nxt[now][s[i] - 'a'])
        now = nxt[now][s[i] - 'a'];
      else
        return;
    }
    ed[now]++;
  }
  void toposort() {
    int ML = 0;
    for (register int i = 1; i <= siz; ++i) cnt[i] = 0;
    for (register int i = 1; i <= siz; ++i) cnt[ml[i]]++, ML = max(ML, ml[i]);
    for (register int i = 1; i <= ML; ++i) cnt[i] += cnt[i - 1];
    for (register int i = 1; i <= siz; ++i) id[cnt[ml[i]]--] = i;
    for (register int i = 1; i <= siz; ++i) ed[id[i]] += ed[fa[id[i]]];
  }
} sam1, sam2;
char s[MAX_N], t[MAX_N];
int main() {
  scanf("%s", s + 1);
  int n;
  scanf("%d", &n);
  sam1.init(), sam2.init();
  sam1.build(s);
  int len = strlen(s + 1);
  reverse(s + 1, s + 1 + len);
  sam2.build(s);
  for (register int i = 1; i <= n; ++i) {
    scanf("%s", t + 1);
    sam1.solve(t);
    int len = strlen(t + 1);
    reverse(t + 1, t + 1 + len);
    sam2.solve(t);
  }
  reverse(sam2.pos + 1, sam2.pos + 1 + len);
  sam1.toposort(), sam2.toposort();
  long long ans = 0;
  for (register int i = 1; i <= len; ++i)
    ans += 1ll * sam1.ed[sam1.pos[i]] * sam2.ed[sam2.pos[i + 1]];
  printf("%lld\n", ans);
  return 0;
}