#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int INF = INT32_MAX;
constexpr int MAXN = 2e5 + 10;
constexpr double eps = 1e-8;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
using Vec = vector<int>;
template <class T>
void Min(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
void Max(T &a, T b) {
  if (b > a) a = b;
}
ll N, M, K, T;
string t, s[MAXN];
constexpr int A = 27;
struct Node {
  Node *to[A];
  int cnt;
} nodes[MAXN * 3];
int szn = 0;
Node *GetNode() {
  assert(szn < MAXN * 3);
  for (int i = (int)(0); i < (int)(A); ++i) nodes[szn].to[i] = nullptr;
  nodes[szn].cnt = 0;
  return &nodes[szn++];
}
void AddWord(Node *v, const string &x) {
  for (int i = (int)(0); i < (int)(x.size()); ++i) {
    int c = x[i] - 'a';
    if (v->to[c] == nullptr) v->to[c] = GetNode();
    v = v->to[c];
  }
  v->cnt++;
}
int CalcCnt(Node *v, const string &x, int pos) {
  int res = 0;
  while (pos < x.size()) {
    int c = x[pos] - 'a';
    if (v->to[c] == nullptr) break;
    v = v->to[c];
    res += v->cnt;
    ++pos;
  }
  return res;
}
Vec ZFun(string x) {
  Vec z(x.size(), 0);
  for (int i = 1, l = 0, r = 0; i < x.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < x.size() && x[z[i]] == x[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
ll Solution() {
  Vec cnt[2];
  M = sqrt(t.size());
  for (int k = (int)(0); k < (int)(2); ++k) {
    cnt[k].assign(t.size() + 1, 0);
    szn = 0;
    Node *root = GetNode();
    for (int i = (int)(0); i < (int)(N); ++i) {
      if (s[i].size() >= M) {
        auto z = ZFun(s[i] + t);
        for (int j = (int)(0); j < (int)(t.size()); ++j)
          cnt[k][j] += z[s[i].size() + j] >= s[i].size();
      } else {
        AddWord(root, s[i]);
      }
    }
    for (int i = (int)(0); i < (int)(t.size()); ++i)
      cnt[k][i] += CalcCnt(root, t, i);
    reverse(t.begin(), t.end());
    for (int i = (int)(0); i < (int)(N); ++i) reverse(s[i].begin(), s[i].end());
  }
  ll ans = 0;
  for (int i = (int)(0); i < (int)(t.size() + 1); ++i)
    ans += 1LL * cnt[0][i] * cnt[1][t.size() - i];
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> t) {
    cin >> N;
    for (int i = (int)(0); i < (int)(N); ++i) cin >> s[i];
    cout << Solution() << '\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;
constexpr int MOD = 1e9 + 7;
constexpr int INF = INT32_MAX;
constexpr int MAXN = 2e5 + 10;
constexpr double eps = 1e-8;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
using Vec = vector<int>;
template <class T>
void Min(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
void Max(T &a, T b) {
  if (b > a) a = b;
}
ll N, M, K, T;
string t, s[MAXN];
constexpr int A = 27;
struct Node {
  Node *to[A];
  int cnt;
} nodes[MAXN * 3];
int szn = 0;
Node *GetNode() {
  assert(szn < MAXN * 3);
  for (int i = (int)(0); i < (int)(A); ++i) nodes[szn].to[i] = nullptr;
  nodes[szn].cnt = 0;
  return &nodes[szn++];
}
void AddWord(Node *v, const string &x) {
  for (int i = (int)(0); i < (int)(x.size()); ++i) {
    int c = x[i] - 'a';
    if (v->to[c] == nullptr) v->to[c] = GetNode();
    v = v->to[c];
  }
  v->cnt++;
}
int CalcCnt(Node *v, const string &x, int pos) {
  int res = 0;
  while (pos < x.size()) {
    int c = x[pos] - 'a';
    if (v->to[c] == nullptr) break;
    v = v->to[c];
    res += v->cnt;
    ++pos;
  }
  return res;
}
Vec ZFun(string x) {
  Vec z(x.size(), 0);
  for (int i = 1, l = 0, r = 0; i < x.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < x.size() && x[z[i]] == x[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
ll Solution() {
  Vec cnt[2];
  M = sqrt(t.size());
  for (int k = (int)(0); k < (int)(2); ++k) {
    cnt[k].assign(t.size() + 1, 0);
    szn = 0;
    Node *root = GetNode();
    for (int i = (int)(0); i < (int)(N); ++i) {
      if (s[i].size() >= M) {
        auto z = ZFun(s[i] + t);
        for (int j = (int)(0); j < (int)(t.size()); ++j)
          cnt[k][j] += z[s[i].size() + j] >= s[i].size();
      } else {
        AddWord(root, s[i]);
      }
    }
    for (int i = (int)(0); i < (int)(t.size()); ++i)
      cnt[k][i] += CalcCnt(root, t, i);
    reverse(t.begin(), t.end());
    for (int i = (int)(0); i < (int)(N); ++i) reverse(s[i].begin(), s[i].end());
  }
  ll ans = 0;
  for (int i = (int)(0); i < (int)(t.size() + 1); ++i)
    ans += 1LL * cnt[0][i] * cnt[1][t.size() - i];
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> t) {
    cin >> N;
    for (int i = (int)(0); i < (int)(N); ++i) cin >> s[i];
    cout << Solution() << '\n';
  }
  return 0;
}

```