#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U>
using Pa = pair<T, U>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
class SuffixArray {
 public:
  vec<int> SA;
  const string S;
  int N;
  SuffixArray(const string& S) : S(S) {
    N = S.size();
    SA.resize(N);
    iota(SA.begin(), SA.end(), 0);
    sort(SA.begin(), SA.end(),
         [&](int i, int j) { return S[i] == S[j] ? i > j : S[i] < S[j]; });
    vec<int> classes(N), C(S.begin(), S.end()), cnt(S.size());
    for (int len = 1; len < N; len <<= 1) {
      for (int i = 0; i < N; i++) {
        if (i > 0 && C[SA[i - 1]] == C[SA[i]] && SA[i - 1] + len < N &&
            C[SA[i - 1] + len / 2] == C[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(cnt.begin(), cnt.end(), 0);
      copy(SA.begin(), SA.end(), C.begin());
      for (int i = 0; i < N; i++) {
        int sl = C[i] - len;
        if (sl >= 0) SA[cnt[classes[sl]]++] = sl;
      }
      classes.swap(C);
    }
  }
  int operator[](int k) const { return SA[k]; }
  int size() const { return N; }
  bool lt_substr(const string& T, int si = 0, int ti = 0) {
    int sn = N, tn = T.size();
    while (si < sn && ti < tn) {
      if (S[si] < T[ti]) return true;
      if (S[si] > T[ti]) return false;
      si++;
      ti++;
    }
    return si >= sn && ti < tn;
  }
  int lower_bound(const string& T, int si = 0, int ti = 0) {
    int l = -1, r = N;
    while (l + 1 < r) {
      int m = (l + r) >> 1;
      (lt_substr(T, SA[m]) ? l : r) = m;
    }
    return r;
  }
  Pa<int, int> lower_upper_bound(string& T) {
    int id = lower_bound(T);
    int l = id - 1, r = N;
    T.back()++;
    while (l + 1 < r) {
      int m = (l + r) >> 1;
      (lt_substr(T, SA[m]) ? l : r) = m;
    }
    T.back()--;
    return {id, r};
  }
};
int main() {
  string S;
  cin >> S;
  int N = S.size();
  int M;
  cin >> M;
  vec<string> T(M);
  for (int i = 0; i < M; i++) cin >> T[i];
  vec<ll> sumL(N + 1, 0);
  SuffixArray SA(S);
  for (int i = 0; i < M; i++) {
    Pa<int, int> p = SA.lower_upper_bound(T[i]);
    sumL[p.first]++;
    sumL[p.second]--;
  }
  for (int i = 1; i <= N; i++) sumL[i] += sumL[i - 1];
  reverse(S.begin(), S.end());
  SuffixArray SA2(S);
  vec<ll> sumR(N + 1, 0);
  for (int i = 0; i < M; i++) {
    reverse(T[i].begin(), T[i].end());
    Pa<int, int> p = SA2.lower_upper_bound(T[i]);
    sumR[p.first]++;
    sumR[p.second]--;
  }
  for (int i = 1; i <= N; i++) sumR[i] += sumR[i - 1];
  vec<ll> valL(N, 0), valR(N, 0);
  for (int i = 0; i < N; i++) valL[SA[i]] = sumL[i];
  for (int i = 0; i < N; i++) valR[SA2[i]] = sumR[i];
  ll ans = 0;
  for (int i = 1; i < N; i++) ans += valL[i] * valR[N - i];
  cout << ans << "\n";
}

### Prompt

In Cpp, your task is to solve 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;
using ll = long long;
template <class T, class U>
using Pa = pair<T, U>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
class SuffixArray {
 public:
  vec<int> SA;
  const string S;
  int N;
  SuffixArray(const string& S) : S(S) {
    N = S.size();
    SA.resize(N);
    iota(SA.begin(), SA.end(), 0);
    sort(SA.begin(), SA.end(),
         [&](int i, int j) { return S[i] == S[j] ? i > j : S[i] < S[j]; });
    vec<int> classes(N), C(S.begin(), S.end()), cnt(S.size());
    for (int len = 1; len < N; len <<= 1) {
      for (int i = 0; i < N; i++) {
        if (i > 0 && C[SA[i - 1]] == C[SA[i]] && SA[i - 1] + len < N &&
            C[SA[i - 1] + len / 2] == C[SA[i] + len / 2]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(cnt.begin(), cnt.end(), 0);
      copy(SA.begin(), SA.end(), C.begin());
      for (int i = 0; i < N; i++) {
        int sl = C[i] - len;
        if (sl >= 0) SA[cnt[classes[sl]]++] = sl;
      }
      classes.swap(C);
    }
  }
  int operator[](int k) const { return SA[k]; }
  int size() const { return N; }
  bool lt_substr(const string& T, int si = 0, int ti = 0) {
    int sn = N, tn = T.size();
    while (si < sn && ti < tn) {
      if (S[si] < T[ti]) return true;
      if (S[si] > T[ti]) return false;
      si++;
      ti++;
    }
    return si >= sn && ti < tn;
  }
  int lower_bound(const string& T, int si = 0, int ti = 0) {
    int l = -1, r = N;
    while (l + 1 < r) {
      int m = (l + r) >> 1;
      (lt_substr(T, SA[m]) ? l : r) = m;
    }
    return r;
  }
  Pa<int, int> lower_upper_bound(string& T) {
    int id = lower_bound(T);
    int l = id - 1, r = N;
    T.back()++;
    while (l + 1 < r) {
      int m = (l + r) >> 1;
      (lt_substr(T, SA[m]) ? l : r) = m;
    }
    T.back()--;
    return {id, r};
  }
};
int main() {
  string S;
  cin >> S;
  int N = S.size();
  int M;
  cin >> M;
  vec<string> T(M);
  for (int i = 0; i < M; i++) cin >> T[i];
  vec<ll> sumL(N + 1, 0);
  SuffixArray SA(S);
  for (int i = 0; i < M; i++) {
    Pa<int, int> p = SA.lower_upper_bound(T[i]);
    sumL[p.first]++;
    sumL[p.second]--;
  }
  for (int i = 1; i <= N; i++) sumL[i] += sumL[i - 1];
  reverse(S.begin(), S.end());
  SuffixArray SA2(S);
  vec<ll> sumR(N + 1, 0);
  for (int i = 0; i < M; i++) {
    reverse(T[i].begin(), T[i].end());
    Pa<int, int> p = SA2.lower_upper_bound(T[i]);
    sumR[p.first]++;
    sumR[p.second]--;
  }
  for (int i = 1; i <= N; i++) sumR[i] += sumR[i - 1];
  vec<ll> valL(N, 0), valR(N, 0);
  for (int i = 0; i < N; i++) valL[SA[i]] = sumL[i];
  for (int i = 0; i < N; i++) valR[SA2[i]] = sumR[i];
  ll ans = 0;
  for (int i = 1; i < N; i++) ans += valL[i] * valR[N - i];
  cout << ans << "\n";
}

```