#include <bits/stdc++.h>
using namespace std;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, a...);
}
const int N = 200 * 1000 + 7;
const int M = 30;
int test;
int n;
long long res;
int trie[N][M];
int ile[N * M];
int link[N * M];
struct Aho {
  int nodeCounter, root;
  void prepare() {
    nodeCounter = 1;
    root = 1;
    for (int i = 0; i < (N); ++i) {
      for (int j = 0; j < (M); ++j) {
        trie[i][j] = 0;
      }
    }
    for (int i = 0; i < (N * M); ++i) {
      ile[i] = link[i] = 0;
    }
  }
  void add(string s) {
    int node = root;
    for (auto it : s) {
      if (trie[node][it - 'a' + 1] == 0) {
        trie[node][it - 'a' + 1] = ++nodeCounter;
      }
      node = trie[node][it - 'a' + 1];
    }
    ile[node]++;
  }
  queue<int> q;
  void build() {
    link[root] = root;
    q.push(root);
    while (!q.empty()) {
      auto it = q.front();
      q.pop();
      for (int i = 1; i <= (26); ++i) {
        int v = trie[it][i];
        if (v != 0) {
          q.push(v);
          link[v] = link[it];
          if (it != root) {
            while (link[v] != root && trie[link[v]][i] == 0) {
              link[v] = link[link[v]];
            }
            if (trie[link[v]][i] != 0) {
              link[v] = trie[link[v]][i];
              ile[v] += ile[link[v]];
            }
          }
        }
      }
    }
  }
  vector<int> doAho(string word) {
    vector<int> odp;
    int node = root;
    for (auto it : word) {
      while (node != root && trie[node][it - 'a' + 1] == 0) {
        node = link[node];
      }
      if (trie[node][it - 'a' + 1] != 0) {
        node = trie[node][it - 'a' + 1];
      }
      odp.push_back(ile[node]);
    }
    return odp;
  }
};
vector<string> pom;
void solve() {
  string word;
  cin >> word;
  cin >> n;
  Aho ahoZwykle;
  ahoZwykle.prepare();
  for (int i = 1; i <= (n); ++i) {
    string s;
    cin >> s;
    pom.push_back(s);
    ahoZwykle.add(s);
  }
  ahoZwykle.build();
  vector<int> a = ahoZwykle.doAho(word);
  ahoZwykle.prepare();
  for (auto s : pom) {
    reverse(s.begin(), s.end());
    ahoZwykle.add(s);
  }
  ahoZwykle.build();
  reverse(word.begin(), word.end());
  vector<int> b = ahoZwykle.doAho(word);
  reverse(b.begin(), b.end());
  for (int i = 0; i < (a.size() - 1); ++i) {
    res += (long long)a[i] * b[i + 1];
  }
  cout << res;
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
  cout << fixed;
  test = 1;
  for (int i = 1; i <= test; i++) {
    solve();
  }
  return 0;
}

### Prompt

Your task is to create 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;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, a...);
}
const int N = 200 * 1000 + 7;
const int M = 30;
int test;
int n;
long long res;
int trie[N][M];
int ile[N * M];
int link[N * M];
struct Aho {
  int nodeCounter, root;
  void prepare() {
    nodeCounter = 1;
    root = 1;
    for (int i = 0; i < (N); ++i) {
      for (int j = 0; j < (M); ++j) {
        trie[i][j] = 0;
      }
    }
    for (int i = 0; i < (N * M); ++i) {
      ile[i] = link[i] = 0;
    }
  }
  void add(string s) {
    int node = root;
    for (auto it : s) {
      if (trie[node][it - 'a' + 1] == 0) {
        trie[node][it - 'a' + 1] = ++nodeCounter;
      }
      node = trie[node][it - 'a' + 1];
    }
    ile[node]++;
  }
  queue<int> q;
  void build() {
    link[root] = root;
    q.push(root);
    while (!q.empty()) {
      auto it = q.front();
      q.pop();
      for (int i = 1; i <= (26); ++i) {
        int v = trie[it][i];
        if (v != 0) {
          q.push(v);
          link[v] = link[it];
          if (it != root) {
            while (link[v] != root && trie[link[v]][i] == 0) {
              link[v] = link[link[v]];
            }
            if (trie[link[v]][i] != 0) {
              link[v] = trie[link[v]][i];
              ile[v] += ile[link[v]];
            }
          }
        }
      }
    }
  }
  vector<int> doAho(string word) {
    vector<int> odp;
    int node = root;
    for (auto it : word) {
      while (node != root && trie[node][it - 'a' + 1] == 0) {
        node = link[node];
      }
      if (trie[node][it - 'a' + 1] != 0) {
        node = trie[node][it - 'a' + 1];
      }
      odp.push_back(ile[node]);
    }
    return odp;
  }
};
vector<string> pom;
void solve() {
  string word;
  cin >> word;
  cin >> n;
  Aho ahoZwykle;
  ahoZwykle.prepare();
  for (int i = 1; i <= (n); ++i) {
    string s;
    cin >> s;
    pom.push_back(s);
    ahoZwykle.add(s);
  }
  ahoZwykle.build();
  vector<int> a = ahoZwykle.doAho(word);
  ahoZwykle.prepare();
  for (auto s : pom) {
    reverse(s.begin(), s.end());
    ahoZwykle.add(s);
  }
  ahoZwykle.build();
  reverse(word.begin(), word.end());
  vector<int> b = ahoZwykle.doAho(word);
  reverse(b.begin(), b.end());
  for (int i = 0; i < (a.size() - 1); ++i) {
    res += (long long)a[i] * b[i + 1];
  }
  cout << res;
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
  cout << fixed;
  test = 1;
  for (int i = 1; i <= test; i++) {
    solve();
  }
  return 0;
}

```