#include <bits/stdc++.h>
using namespace std;
FILE *in = stdin, *out = stdout;
int acN;
struct AC {
  int id;
  int next[26];
  int fail;
  AC() {
    id = 0;
    for (int i = (0); i <= (25); i++) next[i] = -1;
    fail = -1;
  }
};
vector<AC> ac;
int n, m, dy1[200005], dy2[200005];
char a[200005];
int len[200005];
char b[200005];
void input() {
  fscanf(in, "%s", a);
  n = strlen(a);
  fscanf(in, "%d\n", &m);
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    fscanf(in, "%s", b + sum);
    len[i] = strlen(b + sum);
    sum += len[i];
  }
  ac.emplace_back(AC());
}
void buildingPatternsTrie() {
  acN = 0;
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    int cur = 0;
    for (int j = (0); j <= (len[i] - 1); j++) {
      if (ac[cur].next[b[sum + j] - 'a'] == -1) {
        ac.emplace_back(AC());
        ac[cur].next[b[sum + j] - 'a'] = ++acN;
      }
      cur = ac[cur].next[b[sum + j] - 'a'];
    }
    ac[cur].id++;
    sum += len[i];
  }
}
void constructACs() {
  std::queue<int> Q;
  Q.push(0);
  while (!Q.empty()) {
    int node = Q.front();
    Q.pop();
    for (int j = (0); j <= (25); j++) {
      int child = ac[node].next[j];
      if (child == -1) continue;
      Q.push(child);
      int cur = node;
      for (;;) {
        cur = ac[cur].fail;
        if (cur == -1) {
          ac[child].fail = 0;
          break;
        }
        if (ac[cur].next[j] != -1) {
          ac[child].fail = ac[cur].next[j];
          break;
        }
      }
    }
    if (ac[node].fail != -1) ac[node].id += ac[ac[node].fail].id;
  }
}
void pro() {
  buildingPatternsTrie();
  constructACs();
  int cur = 0;
  for (int i = (0); i <= (n - 1); i++) {
    while (ac[cur].next[a[i] - 'a'] == -1) {
      if (ac[cur].fail == -1) break;
      cur = ac[cur].fail;
    }
    if (ac[cur].next[a[i] - 'a'] != -1) {
      cur = ac[cur].next[a[i] - 'a'];
    }
    dy1[i] = ac[cur].id;
  }
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    for (int j = sum, k = sum + len[i] - 1; j < k; j++, k--) {
      swap(b[j], b[k]);
    }
    sum += len[i];
  }
  ac.clear();
  ac.emplace_back(AC());
  buildingPatternsTrie();
  constructACs();
  cur = 0;
  for (int i = n - 1; i >= 0; i--) {
    while (ac[cur].next[a[i] - 'a'] == -1) {
      if (ac[cur].fail == -1) break;
      cur = ac[cur].fail;
    }
    if (ac[cur].next[a[i] - 'a'] != -1) {
      cur = ac[cur].next[a[i] - 'a'];
    }
    dy2[i] = ac[cur].id;
  }
  long long int res = 0;
  for (int i = (0); i <= (n - 1); i++) {
    res += (long long int)dy1[i] * (long long int)dy2[i + 1];
  }
  fprintf(out, "%lld", res);
}
int main() {
  input();
  pro();
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
FILE *in = stdin, *out = stdout;
int acN;
struct AC {
  int id;
  int next[26];
  int fail;
  AC() {
    id = 0;
    for (int i = (0); i <= (25); i++) next[i] = -1;
    fail = -1;
  }
};
vector<AC> ac;
int n, m, dy1[200005], dy2[200005];
char a[200005];
int len[200005];
char b[200005];
void input() {
  fscanf(in, "%s", a);
  n = strlen(a);
  fscanf(in, "%d\n", &m);
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    fscanf(in, "%s", b + sum);
    len[i] = strlen(b + sum);
    sum += len[i];
  }
  ac.emplace_back(AC());
}
void buildingPatternsTrie() {
  acN = 0;
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    int cur = 0;
    for (int j = (0); j <= (len[i] - 1); j++) {
      if (ac[cur].next[b[sum + j] - 'a'] == -1) {
        ac.emplace_back(AC());
        ac[cur].next[b[sum + j] - 'a'] = ++acN;
      }
      cur = ac[cur].next[b[sum + j] - 'a'];
    }
    ac[cur].id++;
    sum += len[i];
  }
}
void constructACs() {
  std::queue<int> Q;
  Q.push(0);
  while (!Q.empty()) {
    int node = Q.front();
    Q.pop();
    for (int j = (0); j <= (25); j++) {
      int child = ac[node].next[j];
      if (child == -1) continue;
      Q.push(child);
      int cur = node;
      for (;;) {
        cur = ac[cur].fail;
        if (cur == -1) {
          ac[child].fail = 0;
          break;
        }
        if (ac[cur].next[j] != -1) {
          ac[child].fail = ac[cur].next[j];
          break;
        }
      }
    }
    if (ac[node].fail != -1) ac[node].id += ac[ac[node].fail].id;
  }
}
void pro() {
  buildingPatternsTrie();
  constructACs();
  int cur = 0;
  for (int i = (0); i <= (n - 1); i++) {
    while (ac[cur].next[a[i] - 'a'] == -1) {
      if (ac[cur].fail == -1) break;
      cur = ac[cur].fail;
    }
    if (ac[cur].next[a[i] - 'a'] != -1) {
      cur = ac[cur].next[a[i] - 'a'];
    }
    dy1[i] = ac[cur].id;
  }
  int sum = 0;
  for (int i = (1); i <= (m); i++) {
    for (int j = sum, k = sum + len[i] - 1; j < k; j++, k--) {
      swap(b[j], b[k]);
    }
    sum += len[i];
  }
  ac.clear();
  ac.emplace_back(AC());
  buildingPatternsTrie();
  constructACs();
  cur = 0;
  for (int i = n - 1; i >= 0; i--) {
    while (ac[cur].next[a[i] - 'a'] == -1) {
      if (ac[cur].fail == -1) break;
      cur = ac[cur].fail;
    }
    if (ac[cur].next[a[i] - 'a'] != -1) {
      cur = ac[cur].next[a[i] - 'a'];
    }
    dy2[i] = ac[cur].id;
  }
  long long int res = 0;
  for (int i = (0); i <= (n - 1); i++) {
    res += (long long int)dy1[i] * (long long int)dy2[i + 1];
  }
  fprintf(out, "%lld", res);
}
int main() {
  input();
  pro();
  return 0;
}

```