#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
inline long long Read() {
  long long s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
const long long A = 3e5 + 5;
long long n;
struct ACM {
  char bk[A];
  char nw[A];
  long long tr[A][26], tot;
  long long val[A];
  long long fail[A], last[A];
  long long ans[A];
  inline void build() {
    long long len = strlen(nw);
    long long p = 0;
    for (long long i = 0; i < len; i++) {
      if (!tr[p][nw[i] - 'a']) tr[p][nw[i] - 'a'] = ++tot;
      p = tr[p][nw[i] - 'a'];
    }
    val[p]++;
    return;
  }
  inline void acm() {
    queue<long long> q;
    long long p = 0;
    for (long long i = 0; i < 26; i++) {
      p = tr[0][i];
      if (!p) continue;
      q.push(p);
      fail[p] = last[p] = 0;
    }
    while (!q.empty()) {
      long long x = q.front();
      q.pop();
      for (long long i = 0; i < 26; i++) {
        p = tr[x][i];
        if (!p) {
          tr[x][i] = tr[fail[x]][i];
          continue;
        }
        q.push(p);
        long long w = fail[x];
        while (w && !tr[w][i]) w = fail[w];
        fail[p] = tr[w][i];
        last[p] = val[fail[p]] ? fail[p] : last[fail[p]];
      }
    }
    return;
  }
  inline void find() {
    long long len = strlen(bk);
    long long p = 0;
    for (long long i = 0; i < len; i++) {
      p = tr[p][bk[i] - 'a'];
      long long res = 0;
      long long w = val[p] ? p : last[p];
      while (w) {
        res += val[w];
        w = last[w];
      }
      ans[i] = res;
    }
    return;
  }
} tr1, tr2;
long long res = 0;
inline void get_ans() {
  long long len = strlen(tr1.bk);
  for (long long i = 0; i < len - 1; i++)
    res += tr1.ans[i] * tr2.ans[len - i - 2];
  return;
}
signed main() {
  scanf("%s", tr1.bk);
  memcpy(tr2.bk, tr1.bk, sizeof(tr2.bk));
  reverse(tr2.bk, tr2.bk + strlen(tr2.bk));
  n = Read();
  for (long long i = 1; i <= n; i++) {
    scanf("%s", tr1.nw);
    tr1.build();
    memcpy(tr2.nw, tr1.nw, sizeof(tr2.nw));
    reverse(tr2.nw, tr2.nw + strlen(tr2.nw));
    tr2.build();
  }
  tr1.acm();
  tr2.acm();
  tr1.find();
  tr2.find();
  get_ans();
  printf("%lld\n", res);
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
inline long long Read() {
  long long s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
const long long A = 3e5 + 5;
long long n;
struct ACM {
  char bk[A];
  char nw[A];
  long long tr[A][26], tot;
  long long val[A];
  long long fail[A], last[A];
  long long ans[A];
  inline void build() {
    long long len = strlen(nw);
    long long p = 0;
    for (long long i = 0; i < len; i++) {
      if (!tr[p][nw[i] - 'a']) tr[p][nw[i] - 'a'] = ++tot;
      p = tr[p][nw[i] - 'a'];
    }
    val[p]++;
    return;
  }
  inline void acm() {
    queue<long long> q;
    long long p = 0;
    for (long long i = 0; i < 26; i++) {
      p = tr[0][i];
      if (!p) continue;
      q.push(p);
      fail[p] = last[p] = 0;
    }
    while (!q.empty()) {
      long long x = q.front();
      q.pop();
      for (long long i = 0; i < 26; i++) {
        p = tr[x][i];
        if (!p) {
          tr[x][i] = tr[fail[x]][i];
          continue;
        }
        q.push(p);
        long long w = fail[x];
        while (w && !tr[w][i]) w = fail[w];
        fail[p] = tr[w][i];
        last[p] = val[fail[p]] ? fail[p] : last[fail[p]];
      }
    }
    return;
  }
  inline void find() {
    long long len = strlen(bk);
    long long p = 0;
    for (long long i = 0; i < len; i++) {
      p = tr[p][bk[i] - 'a'];
      long long res = 0;
      long long w = val[p] ? p : last[p];
      while (w) {
        res += val[w];
        w = last[w];
      }
      ans[i] = res;
    }
    return;
  }
} tr1, tr2;
long long res = 0;
inline void get_ans() {
  long long len = strlen(tr1.bk);
  for (long long i = 0; i < len - 1; i++)
    res += tr1.ans[i] * tr2.ans[len - i - 2];
  return;
}
signed main() {
  scanf("%s", tr1.bk);
  memcpy(tr2.bk, tr1.bk, sizeof(tr2.bk));
  reverse(tr2.bk, tr2.bk + strlen(tr2.bk));
  n = Read();
  for (long long i = 1; i <= n; i++) {
    scanf("%s", tr1.nw);
    tr1.build();
    memcpy(tr2.nw, tr1.nw, sizeof(tr2.nw));
    reverse(tr2.nw, tr2.nw + strlen(tr2.nw));
    tr2.build();
  }
  tr1.acm();
  tr2.acm();
  tr1.find();
  tr2.find();
  get_ans();
  printf("%lld\n", res);
  return 0;
}

```