#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef struct Node {
  int son[26], Fail, End, Cnt;
  void Clear() {
    memset(son, 0, sizeof son);
    Fail = End = Cnt = 0;
  }
  int& operator[](int x) { return son[x]; }
} Node;
Node Trie[N], Trie1[N];
char s[N], t[N];
int Ans, idx = 1, n, Head, Tail;
int Mp[N], vis[N], Ind[N], Q[N];
void Insert(char s[], int Id) {
  int p = 1;
  for (int i = 0; s[i]; i++) {
    int t = s[i] - 'a';
    if (!Trie[p][t]) Trie[p][t] = ++idx;
    p = Trie[p][t];
  }
  Trie[p].Cnt++;
}
void Insert1(char s[], int Id) {
  int p = 1;
  for (int i = 0; s[i]; i++) {
    int t = s[i] - 'a';
    if (!Trie1[p][t]) Trie1[p][t] = ++idx;
    p = Trie1[p][t];
  }
  Trie1[p].Cnt++;
}
void Build() {
  Head = 1, Tail = 0;
  for (int i = 0; i < 26; i++) {
    Trie[0][i] = 1;
  }
  Q[++Tail] = 1;
  while (Head <= Tail) {
    int u = Q[Head++];
    Trie[u].Cnt += Trie[Trie[u].Fail].Cnt;
    for (int i = 0; i < 26; i++) {
      int To = Trie[u][i];
      if (To) {
        Trie[To].Fail = Trie[Trie[u].Fail][i];
        Ind[Trie[To].Fail]++;
        Q[++Tail] = Trie[u][i];
      } else {
        Trie[u][i] = Trie[Trie[u].Fail][i];
      }
    }
  }
}
void Build1() {
  Head = 1, Tail = 0;
  for (int i = 0; i < 26; i++) {
    Trie1[0][i] = 1;
  }
  Q[++Tail] = 1;
  while (Head <= Tail) {
    int u = Q[Head++];
    Trie1[u].Cnt += Trie1[Trie1[u].Fail].Cnt;
    for (int i = 0; i < 26; i++) {
      int To = Trie1[u][i];
      if (To) {
        Trie1[To].Fail = Trie1[Trie1[u].Fail][i];
        Ind[Trie1[To].Fail]++;
        Q[++Tail] = Trie1[u][i];
      } else {
        Trie1[u][i] = Trie1[Trie1[u].Fail][i];
      }
    }
  }
}
long long st[N], ed[N];
void getans(char s[]) {
  int p = 1;
  long long ans = 0;
  for (int i = 0; s[i]; i++) {
    p = Trie[p][s[i] - 'a'];
    st[i] = Trie[p].Cnt;
  }
}
void getans1(char s[], int len) {
  int p = 1;
  long long ans = 0;
  for (int i = len - 1; i >= 0; i--) {
    p = Trie1[p][s[i] - 'a'];
    ed[i] = Trie1[p].Cnt;
  }
}
int main() {
  scanf("%s", t);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    Insert(s, i);
    int m1 = strlen(s);
    reverse(s, s + m1);
    Insert1(s, i);
  }
  Build();
  Build1();
  getans(t);
  int len = strlen(t);
  getans1(t, len);
  long long ans = 0;
  for (int i = 0; i < len - 1; i++) {
    ans += st[i] * ed[i + 1];
  }
  printf("%lld\n", ans);
}

### Prompt

Generate 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>
using namespace std;
const int N = 5e5 + 10;
typedef struct Node {
  int son[26], Fail, End, Cnt;
  void Clear() {
    memset(son, 0, sizeof son);
    Fail = End = Cnt = 0;
  }
  int& operator[](int x) { return son[x]; }
} Node;
Node Trie[N], Trie1[N];
char s[N], t[N];
int Ans, idx = 1, n, Head, Tail;
int Mp[N], vis[N], Ind[N], Q[N];
void Insert(char s[], int Id) {
  int p = 1;
  for (int i = 0; s[i]; i++) {
    int t = s[i] - 'a';
    if (!Trie[p][t]) Trie[p][t] = ++idx;
    p = Trie[p][t];
  }
  Trie[p].Cnt++;
}
void Insert1(char s[], int Id) {
  int p = 1;
  for (int i = 0; s[i]; i++) {
    int t = s[i] - 'a';
    if (!Trie1[p][t]) Trie1[p][t] = ++idx;
    p = Trie1[p][t];
  }
  Trie1[p].Cnt++;
}
void Build() {
  Head = 1, Tail = 0;
  for (int i = 0; i < 26; i++) {
    Trie[0][i] = 1;
  }
  Q[++Tail] = 1;
  while (Head <= Tail) {
    int u = Q[Head++];
    Trie[u].Cnt += Trie[Trie[u].Fail].Cnt;
    for (int i = 0; i < 26; i++) {
      int To = Trie[u][i];
      if (To) {
        Trie[To].Fail = Trie[Trie[u].Fail][i];
        Ind[Trie[To].Fail]++;
        Q[++Tail] = Trie[u][i];
      } else {
        Trie[u][i] = Trie[Trie[u].Fail][i];
      }
    }
  }
}
void Build1() {
  Head = 1, Tail = 0;
  for (int i = 0; i < 26; i++) {
    Trie1[0][i] = 1;
  }
  Q[++Tail] = 1;
  while (Head <= Tail) {
    int u = Q[Head++];
    Trie1[u].Cnt += Trie1[Trie1[u].Fail].Cnt;
    for (int i = 0; i < 26; i++) {
      int To = Trie1[u][i];
      if (To) {
        Trie1[To].Fail = Trie1[Trie1[u].Fail][i];
        Ind[Trie1[To].Fail]++;
        Q[++Tail] = Trie1[u][i];
      } else {
        Trie1[u][i] = Trie1[Trie1[u].Fail][i];
      }
    }
  }
}
long long st[N], ed[N];
void getans(char s[]) {
  int p = 1;
  long long ans = 0;
  for (int i = 0; s[i]; i++) {
    p = Trie[p][s[i] - 'a'];
    st[i] = Trie[p].Cnt;
  }
}
void getans1(char s[], int len) {
  int p = 1;
  long long ans = 0;
  for (int i = len - 1; i >= 0; i--) {
    p = Trie1[p][s[i] - 'a'];
    ed[i] = Trie1[p].Cnt;
  }
}
int main() {
  scanf("%s", t);
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    Insert(s, i);
    int m1 = strlen(s);
    reverse(s, s + m1);
    Insert1(s, i);
  }
  Build();
  Build1();
  getans(t);
  int len = strlen(t);
  getans1(t, len);
  long long ans = 0;
  for (int i = 0; i < len - 1; i++) {
    ans += st[i] * ed[i + 1];
  }
  printf("%lld\n", ans);
}

```