#include <bits/stdc++.h>
using namespace std;
long long n, m;
const long long NALPHABET = 26;
struct Node {
  Node **children, **go;
  bool leaf;
  char charToParent;
  Node *parent, *suffLink, *dictSuffLink;
  long long count;
  Node() {
    children = new Node*[NALPHABET];
    go = new Node*[NALPHABET];
    for (long long i = 0; i < NALPHABET; i++) {
      children[i] = go[i] = NULL;
    }
    parent = suffLink = dictSuffLink = NULL;
    leaf = false;
    count = 0;
  }
};
Node* createRoot() {
  Node* node = new Node();
  node->suffLink = node;
  return node;
}
void addString(Node* node, const string& s) {
  for (long long i = 0; i < s.length(); i++) {
    long long c = s[i] - 'a';
    if (node->children[c] == NULL) {
      Node* n = new Node();
      n->parent = node;
      n->charToParent = s[i];
      node->children[c] = n;
    }
    node = node->children[c];
  }
  node->leaf = true;
  node->count++;
}
Node* go(Node* node, char ch);
Node* suffLink(Node* node) {
  if (node->suffLink == NULL) {
    if (node->parent->parent == NULL) {
      node->suffLink = node->parent;
    } else {
      node->suffLink = go(suffLink(node->parent), node->charToParent);
    }
  }
  return node->suffLink;
}
Node* dictSuffLink(Node* node) {
  if (node->dictSuffLink == NULL) {
    Node* n = suffLink(node);
    if (node == n) {
      node->dictSuffLink = node;
    } else {
      while (!n->leaf && n->parent != NULL) {
        n = dictSuffLink(n);
      }
      node->dictSuffLink = n;
    }
  }
  return node->dictSuffLink;
}
Node* go(Node* node, char ch) {
  long long c = ch - 'a';
  if (node->go[c] == NULL) {
    if (node->children[c] != NULL) {
      node->go[c] = node->children[c];
    } else {
      node->go[c] = node->parent == NULL ? node : go(suffLink(node), ch);
    }
  }
  return node->go[c];
}
long long calc(Node* node) {
  if (node->parent == NULL) {
    return 0;
  } else {
    return node->count + calc(dictSuffLink(node));
  }
}
string AA;
long long N;
string tab[200100];
long long beg[500100], en[500100];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Node* root = createRoot();
  cin >> AA;
  cin >> N;
  for (long long i = 0; i < N; i++) {
    cin >> tab[i];
    addString(root, tab[i]);
  }
  Node* node = root;
  for (long long i = 0; i < AA.length(); i++) {
    node = go(node, AA[i]);
    Node* temp = node;
    while (temp != root) {
      if (temp->leaf) {
        en[i + 1] += temp->count;
      }
      temp = dictSuffLink(temp);
    }
  }
  Node* root2 = createRoot();
  for (long long i = 0; i < N; i++) {
    reverse(tab[i].begin(), tab[i].end());
    addString(root2, tab[i]);
  }
  reverse(AA.begin(), AA.end());
  Node* node2 = root2;
  long long len = AA.length();
  for (long long i = 0; i < AA.length(); i++) {
    node2 = go(node2, AA[i]);
    Node* temp = node2;
    while (temp != root2) {
      if (temp->leaf) {
        beg[len - i - 1] += temp->count;
      }
      temp = dictSuffLink(temp);
    }
  }
  long long ans = 0;
  for (long long i = 0; i < AA.length(); i++) {
    ans += beg[i] * en[i];
  }
  cout << ans << endl;
  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;
long long n, m;
const long long NALPHABET = 26;
struct Node {
  Node **children, **go;
  bool leaf;
  char charToParent;
  Node *parent, *suffLink, *dictSuffLink;
  long long count;
  Node() {
    children = new Node*[NALPHABET];
    go = new Node*[NALPHABET];
    for (long long i = 0; i < NALPHABET; i++) {
      children[i] = go[i] = NULL;
    }
    parent = suffLink = dictSuffLink = NULL;
    leaf = false;
    count = 0;
  }
};
Node* createRoot() {
  Node* node = new Node();
  node->suffLink = node;
  return node;
}
void addString(Node* node, const string& s) {
  for (long long i = 0; i < s.length(); i++) {
    long long c = s[i] - 'a';
    if (node->children[c] == NULL) {
      Node* n = new Node();
      n->parent = node;
      n->charToParent = s[i];
      node->children[c] = n;
    }
    node = node->children[c];
  }
  node->leaf = true;
  node->count++;
}
Node* go(Node* node, char ch);
Node* suffLink(Node* node) {
  if (node->suffLink == NULL) {
    if (node->parent->parent == NULL) {
      node->suffLink = node->parent;
    } else {
      node->suffLink = go(suffLink(node->parent), node->charToParent);
    }
  }
  return node->suffLink;
}
Node* dictSuffLink(Node* node) {
  if (node->dictSuffLink == NULL) {
    Node* n = suffLink(node);
    if (node == n) {
      node->dictSuffLink = node;
    } else {
      while (!n->leaf && n->parent != NULL) {
        n = dictSuffLink(n);
      }
      node->dictSuffLink = n;
    }
  }
  return node->dictSuffLink;
}
Node* go(Node* node, char ch) {
  long long c = ch - 'a';
  if (node->go[c] == NULL) {
    if (node->children[c] != NULL) {
      node->go[c] = node->children[c];
    } else {
      node->go[c] = node->parent == NULL ? node : go(suffLink(node), ch);
    }
  }
  return node->go[c];
}
long long calc(Node* node) {
  if (node->parent == NULL) {
    return 0;
  } else {
    return node->count + calc(dictSuffLink(node));
  }
}
string AA;
long long N;
string tab[200100];
long long beg[500100], en[500100];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Node* root = createRoot();
  cin >> AA;
  cin >> N;
  for (long long i = 0; i < N; i++) {
    cin >> tab[i];
    addString(root, tab[i]);
  }
  Node* node = root;
  for (long long i = 0; i < AA.length(); i++) {
    node = go(node, AA[i]);
    Node* temp = node;
    while (temp != root) {
      if (temp->leaf) {
        en[i + 1] += temp->count;
      }
      temp = dictSuffLink(temp);
    }
  }
  Node* root2 = createRoot();
  for (long long i = 0; i < N; i++) {
    reverse(tab[i].begin(), tab[i].end());
    addString(root2, tab[i]);
  }
  reverse(AA.begin(), AA.end());
  Node* node2 = root2;
  long long len = AA.length();
  for (long long i = 0; i < AA.length(); i++) {
    node2 = go(node2, AA[i]);
    Node* temp = node2;
    while (temp != root2) {
      if (temp->leaf) {
        beg[len - i - 1] += temp->count;
      }
      temp = dictSuffLink(temp);
    }
  }
  long long ans = 0;
  for (long long i = 0; i < AA.length(); i++) {
    ans += beg[i] * en[i];
  }
  cout << ans << endl;
  return 0;
}

```