#include <bits/stdc++.h>
using namespace std;
struct aho {
  const static int MAXL = 200005;
  struct node {
    int dic[27], parent, link;
    long long l;
    node(int p) {
      parent = p;
      link = l = 0;
      for (int i = 0; i < 26; i++) dic[i] = -1;
    }
  };
  queue<pair<int, int> > Q;
  vector<node> tree;
  aho() { tree.push_back(node(0)); }
  int f(char c) { return c - 'a'; }
  void add_word(char *W) {
    int l = strlen(W), nod = 0;
    for (int i = 0; i < l; i++) {
      if (tree[nod].dic[f(W[i])] == -1)
        tree[nod].dic[f(W[i])] = tree.size(), tree.push_back(node(nod));
      nod = tree[nod].dic[f(W[i])];
    }
    tree[nod].l++;
  }
  void links() {
    Q.push(pair<int, int>(0, 0));
    int nodo, car;
    while (!Q.empty()) {
      nodo = Q.front().first;
      car = Q.front().second;
      Q.pop();
      for (int i = 0; i < 26; i++)
        if (tree[nodo].dic[i] != -1)
          Q.push(pair<int, int>(tree[nodo].dic[i], i));
      if (nodo == 0 || tree[0].dic[car] == nodo) continue;
      int &link = tree[nodo].link;
      link = tree[tree[nodo].parent].link;
      while (link && tree[link].dic[car] == -1) link = tree[link].link;
      link = tree[link].dic[car];
      if (link == -1) link++;
      tree[nodo].l += tree[link].l;
    }
  }
  int go(int nodo, int car) {
    if (tree[nodo].dic[car] != -1) return tree[nodo].dic[car];
    int link = tree[nodo].link;
    while (link && tree[link].dic[car] == -1) link = tree[link].link;
    link = tree[link].dic[car];
    if (link == -1) link++;
    return link;
  }
} nor, rev;
const int maxn = 200005;
char s[maxn], a[maxn];
long long n, T[maxn], Tr[maxn];
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> s >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    int l = strlen(a);
    nor.add_word(a);
    reverse(a, a + l);
    rev.add_word(a);
  }
  nor.links();
  rev.links();
  int l = strlen(s);
  int nod = 0;
  for (int i = 0; i < l; i++) {
    nod = nor.go(nod, nor.f(s[i]));
    T[i] = nor.tree[nod].l;
  }
  nod = 0;
  for (int i = l - 1; i >= 0; i--) {
    nod = rev.go(nod, nor.f(s[i]));
    Tr[i] = rev.tree[nod].l;
  }
  long long sol = 0;
  for (int i = 0; i < l - 1; i++) sol += T[i] * Tr[i + 1];
  cout << sol << "\n";
  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;
struct aho {
  const static int MAXL = 200005;
  struct node {
    int dic[27], parent, link;
    long long l;
    node(int p) {
      parent = p;
      link = l = 0;
      for (int i = 0; i < 26; i++) dic[i] = -1;
    }
  };
  queue<pair<int, int> > Q;
  vector<node> tree;
  aho() { tree.push_back(node(0)); }
  int f(char c) { return c - 'a'; }
  void add_word(char *W) {
    int l = strlen(W), nod = 0;
    for (int i = 0; i < l; i++) {
      if (tree[nod].dic[f(W[i])] == -1)
        tree[nod].dic[f(W[i])] = tree.size(), tree.push_back(node(nod));
      nod = tree[nod].dic[f(W[i])];
    }
    tree[nod].l++;
  }
  void links() {
    Q.push(pair<int, int>(0, 0));
    int nodo, car;
    while (!Q.empty()) {
      nodo = Q.front().first;
      car = Q.front().second;
      Q.pop();
      for (int i = 0; i < 26; i++)
        if (tree[nodo].dic[i] != -1)
          Q.push(pair<int, int>(tree[nodo].dic[i], i));
      if (nodo == 0 || tree[0].dic[car] == nodo) continue;
      int &link = tree[nodo].link;
      link = tree[tree[nodo].parent].link;
      while (link && tree[link].dic[car] == -1) link = tree[link].link;
      link = tree[link].dic[car];
      if (link == -1) link++;
      tree[nodo].l += tree[link].l;
    }
  }
  int go(int nodo, int car) {
    if (tree[nodo].dic[car] != -1) return tree[nodo].dic[car];
    int link = tree[nodo].link;
    while (link && tree[link].dic[car] == -1) link = tree[link].link;
    link = tree[link].dic[car];
    if (link == -1) link++;
    return link;
  }
} nor, rev;
const int maxn = 200005;
char s[maxn], a[maxn];
long long n, T[maxn], Tr[maxn];
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> s >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    int l = strlen(a);
    nor.add_word(a);
    reverse(a, a + l);
    rev.add_word(a);
  }
  nor.links();
  rev.links();
  int l = strlen(s);
  int nod = 0;
  for (int i = 0; i < l; i++) {
    nod = nor.go(nod, nor.f(s[i]));
    T[i] = nor.tree[nod].l;
  }
  nod = 0;
  for (int i = l - 1; i >= 0; i--) {
    nod = rev.go(nod, nor.f(s[i]));
    Tr[i] = rev.tree[nod].l;
  }
  long long sol = 0;
  for (int i = 0; i < l - 1; i++) sol += T[i] * Tr[i + 1];
  cout << sol << "\n";
  return 0;
}

```