#include <bits/stdc++.h>
using namespace std;
template <typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
  return os << '(' << pai.first << ' ' << pai.second << ')';
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
  cout << '[';
  for (auto p : v) cout << p << ",";
  cout << "]";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T>
void get_max(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void get_min(T &a, T b) {
  a = min(a, b);
}
const int MAXN = 200005, MAXC = 26;
struct aho_corasick {
  int trans[MAXN + 1][MAXC];
  int fail[MAXN + 1];
  long long term[MAXN + 1];
  void build(const vector<string> &v) {
    memset(trans, 0, sizeof(trans)), memset(fail, 0, sizeof(fail)),
        memset(term, 0, sizeof(term));
    int cnode = 1;
    for (auto &s : (v)) {
      int p = 0;
      for (auto &j : (s)) {
        char c = j - 'a';
        if (!trans[p][c]) trans[p][c] = cnode++;
        p = trans[p][c];
      }
      term[p]++;
    }
    queue<int> q;
    for (int i = 0, _i = (MAXC); i < _i; i++)
      if (trans[0][i]) q.push(trans[0][i]);
    while (!q.empty()) {
      int t = q.front();
      q.pop();
      for (int i = 0, _i = (MAXC); i < _i; i++) {
        if (trans[t][i]) {
          int p = fail[t];
          while (p and not trans[p][i]) p = fail[p];
          p = trans[p][i];
          fail[trans[t][i]] = p;
          term[trans[t][i]] += term[p];
          q.push(trans[t][i]);
        }
      }
    }
  }
  void query(string &t, long long *res) {
    int p = 0;
    for (int x = 0, _x = (((int)(t).size())); x < _x; x++) {
      char c = t[x] - 'a';
      while (p and not trans[p][c]) {
        p = fail[p];
      }
      p = trans[p][c];
      res[x] = term[p];
    }
  }
} prv, inv;
int N;
vector<string> a;
vector<string> b;
string A, B;
long long res1[200000], res2[200000];
int main(void) {
  iostream::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> A >> N;
  for (int i = 0, _i = (N); i < _i; i++) {
    string t;
    cin >> t;
    a.push_back(t);
    reverse((t).begin(), (t).end());
    b.push_back(t);
  }
  prv.build(a);
  inv.build(b);
  prv.query(A, res1);
  reverse((A).begin(), (A).end());
  inv.query(A, res2);
  reverse(res2, res2 + ((int)(A).size()));
  for (int i = 0, _i = (((int)(A).size())); i < _i; i++) 0;
  long long res = 0;
  for (int i = 0, _i = (((int)(A).size()) - 1); i < _i; i++)
    res += (long long)res1[i] * res2[i + 1];
  cout << res << '\n';
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 <typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
  return os << '(' << pai.first << ' ' << pai.second << ')';
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
  cout << '[';
  for (auto p : v) cout << p << ",";
  cout << "]";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T>
void get_max(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void get_min(T &a, T b) {
  a = min(a, b);
}
const int MAXN = 200005, MAXC = 26;
struct aho_corasick {
  int trans[MAXN + 1][MAXC];
  int fail[MAXN + 1];
  long long term[MAXN + 1];
  void build(const vector<string> &v) {
    memset(trans, 0, sizeof(trans)), memset(fail, 0, sizeof(fail)),
        memset(term, 0, sizeof(term));
    int cnode = 1;
    for (auto &s : (v)) {
      int p = 0;
      for (auto &j : (s)) {
        char c = j - 'a';
        if (!trans[p][c]) trans[p][c] = cnode++;
        p = trans[p][c];
      }
      term[p]++;
    }
    queue<int> q;
    for (int i = 0, _i = (MAXC); i < _i; i++)
      if (trans[0][i]) q.push(trans[0][i]);
    while (!q.empty()) {
      int t = q.front();
      q.pop();
      for (int i = 0, _i = (MAXC); i < _i; i++) {
        if (trans[t][i]) {
          int p = fail[t];
          while (p and not trans[p][i]) p = fail[p];
          p = trans[p][i];
          fail[trans[t][i]] = p;
          term[trans[t][i]] += term[p];
          q.push(trans[t][i]);
        }
      }
    }
  }
  void query(string &t, long long *res) {
    int p = 0;
    for (int x = 0, _x = (((int)(t).size())); x < _x; x++) {
      char c = t[x] - 'a';
      while (p and not trans[p][c]) {
        p = fail[p];
      }
      p = trans[p][c];
      res[x] = term[p];
    }
  }
} prv, inv;
int N;
vector<string> a;
vector<string> b;
string A, B;
long long res1[200000], res2[200000];
int main(void) {
  iostream::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> A >> N;
  for (int i = 0, _i = (N); i < _i; i++) {
    string t;
    cin >> t;
    a.push_back(t);
    reverse((t).begin(), (t).end());
    b.push_back(t);
  }
  prv.build(a);
  inv.build(b);
  prv.query(A, res1);
  reverse((A).begin(), (A).end());
  inv.query(A, res2);
  reverse(res2, res2 + ((int)(A).size()));
  for (int i = 0, _i = (((int)(A).size())); i < _i; i++) 0;
  long long res = 0;
  for (int i = 0, _i = (((int)(A).size()) - 1); i < _i; i++)
    res += (long long)res1[i] * res2[i + 1];
  cout << res << '\n';
}

```