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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400005;
struct node {
  int suff_link, par;
  char c;
  map<char, int> go;
  int is_word;
  node() {
    suff_link = -1, par = -1;
    is_word = 0;
  }
};
int n;
char s[MAXN];
vector<node> trie;
void trieInsert(const char *s) {
  int cur_node = 0;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int go = trie[cur_node].go[s[i]];
    if (go == 0) {
      node add;
      add.par = cur_node;
      add.c = s[i];
      trie.push_back(add);
      go = (int)trie.size() - 1;
      trie[cur_node].go[s[i]] = go;
    }
    cur_node = go;
  }
  trie[cur_node].is_word++;
}
int go(int cur_node, char c);
int getSuffLink(int cur_node) {
  if (trie[cur_node].suff_link != -1) return trie[cur_node].suff_link;
  if (trie[cur_node].par == 0) return trie[cur_node].suff_link = 0;
  char c = trie[cur_node].c;
  int parent = trie[cur_node].par;
  return trie[cur_node].suff_link = go(trie[parent].suff_link, c);
}
int go(int cur_node, char c) {
  if (trie[cur_node].go.count(c) > 0) return trie[cur_node].go[c];
  if (cur_node == 0) return trie[cur_node].go[c] = 0;
  int suff_link = getSuffLink(cur_node);
  return trie[cur_node].go[c] = go(suff_link, c);
}
void buildAhoCorasick() {
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int cur_node = q.front();
    q.pop();
    for (map<char, int>::iterator it = trie[cur_node].go.begin();
         it != trie[cur_node].go.end(); it++) {
      q.push(it->second);
    }
    int suff_link = getSuffLink(cur_node);
    trie[cur_node].suff_link = suff_link;
    if (trie[suff_link].is_word)
      trie[cur_node].is_word += trie[suff_link].is_word;
  }
}
char str[MAXN];
int main() {
  scanf("%s", str);
  vector<string> wr;
  vector<int> pre;
  {
    node root;
    root.suff_link = 0;
    trie.push_back(root);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%s", s);
      trieInsert(s);
      wr.push_back(s);
    }
    buildAhoCorasick();
    int cur_node = 0;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
      cur_node = go(cur_node, str[i]);
      pre.push_back(trie[cur_node].is_word);
    }
    trie.clear();
  }
  node root;
  root.suff_link = 0;
  trie.push_back(root);
  for (auto &s : wr) {
    reverse(s.begin(), s.end());
    trieInsert(s.c_str());
  }
  buildAhoCorasick();
  int cur_node = 0;
  int len = strlen(str);
  long long res = 0;
  long long last = 0;
  for (int i = len - 1; i >= 0; --i) {
    cur_node = go(cur_node, str[i]);
    long long x = trie[cur_node].is_word;
    res += pre[i] * last;
    last = x;
  }
  cout << res << endl;
  return 0;
}