#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
using namespace std;
vector<long long> SA(long long n, string &v) {
  vector<long long> sa(n), tmp(n), rnk(n);
  for (long long i = 0; i < n; i++) sa[i] = i, rnk[i] = v[i];
  for (long long k = 0; tmp[sa[n - 1]] != n - 1; k = k ? k * 2 : 1) {
    auto cmp = [&](long long i, long long j) {
      return rnk[i] != rnk[j]           ? rnk[i] < rnk[j]
             : (i + k < n && j + k < n) ? rnk[i + k] < rnk[j + k]
                                        : i > j;
    };
    {
      long long N = max(n, 128LL);
      vector<long long> cmp(N), tmp(n);
      for (long long i = 0; i < n; i++) cmp[rnk[i]]++;
      for (long long i = 1; i < N; i++) cmp[i] += cmp[i - 1];
      for (long long i = n - 1; i >= 0; i--)
        if (sa[i] >= k) tmp[--cmp[rnk[sa[i] - k]]] = sa[i] - k;
      for (long long i = n - 1; i >= 0; i--)
        if (sa[i] >= n - k) tmp[--cmp[rnk[sa[i]]]] = sa[i];
      sa = tmp;
    }
    for (long long i = 1; i < n; i++)
      tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
    rnk = tmp;
  }
  return sa;
}
vector<long long> RNK(long long n, vector<long long> &sa) {
  vector<long long> rnk(n);
  for (long long i = 0; i < n; i++) rnk[sa[i]] = i;
  return rnk;
}
vector<string> pv, rpv;
vector<long long> bld(string &v, vector<long long> &sa, vector<string> &pv) {
  long long n = v.size();
  vector<long long> prf(n);
  for (string &xv : pv) {
    struct cmpstr {
      string &v;
      bool operator()(long long i, string s) const {
        return lexicographical_compare(v.begin() + i, v.end(), s.begin(),
                                       s.end());
      };
      bool operator()(string s, long long i) const {
        return lexicographical_compare(s.begin(), s.end(), v.begin() + i,
                                       v.end());
      };
    } cmp{v};
    auto it = lower_bound(sa.begin(), sa.end(), xv, cmp);
    if (it != sa.end()) prf[it - sa.begin()]++;
    it = upper_bound(sa.begin(), sa.end(), xv + char(127), cmp);
    if (it != sa.end()) prf[it - sa.begin()]--;
  }
  for (long long i = 1; i < n; i++) prf[i] += prf[i - 1];
  return prf;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ;
  string v;
  cin >> v;
  long long xn;
  cin >> xn;
  pv.resize(xn), rpv.resize(xn);
  for (long long i = 0; i < xn; i++)
    cin >> pv[i], rpv[i] = string(pv[i].rbegin(), pv[i].rend());
  long long n = v.length();
  string rv = string(v.rbegin(), v.rend());
  vector<long long> sa1 = SA(n, v), sa2 = SA(n, rv);
  vector<long long> s1 = bld(v, sa1, pv), s2 = bld(rv, sa2, rpv);
  vector<long long> r1 = RNK(n, sa1), r2 = RNK(n, sa2);
  long long sum = 0;
  reverse(r2.begin(), r2.end());
  for (long long i = 1; i < n; i++) sum += s2[r2[i - 1]] * s1[r1[i]];
  cout << sum << '\n';
}

### Prompt

Please formulate 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>
#pragma GCC optimize "Ofast"
using namespace std;
vector<long long> SA(long long n, string &v) {
  vector<long long> sa(n), tmp(n), rnk(n);
  for (long long i = 0; i < n; i++) sa[i] = i, rnk[i] = v[i];
  for (long long k = 0; tmp[sa[n - 1]] != n - 1; k = k ? k * 2 : 1) {
    auto cmp = [&](long long i, long long j) {
      return rnk[i] != rnk[j]           ? rnk[i] < rnk[j]
             : (i + k < n && j + k < n) ? rnk[i + k] < rnk[j + k]
                                        : i > j;
    };
    {
      long long N = max(n, 128LL);
      vector<long long> cmp(N), tmp(n);
      for (long long i = 0; i < n; i++) cmp[rnk[i]]++;
      for (long long i = 1; i < N; i++) cmp[i] += cmp[i - 1];
      for (long long i = n - 1; i >= 0; i--)
        if (sa[i] >= k) tmp[--cmp[rnk[sa[i] - k]]] = sa[i] - k;
      for (long long i = n - 1; i >= 0; i--)
        if (sa[i] >= n - k) tmp[--cmp[rnk[sa[i]]]] = sa[i];
      sa = tmp;
    }
    for (long long i = 1; i < n; i++)
      tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
    rnk = tmp;
  }
  return sa;
}
vector<long long> RNK(long long n, vector<long long> &sa) {
  vector<long long> rnk(n);
  for (long long i = 0; i < n; i++) rnk[sa[i]] = i;
  return rnk;
}
vector<string> pv, rpv;
vector<long long> bld(string &v, vector<long long> &sa, vector<string> &pv) {
  long long n = v.size();
  vector<long long> prf(n);
  for (string &xv : pv) {
    struct cmpstr {
      string &v;
      bool operator()(long long i, string s) const {
        return lexicographical_compare(v.begin() + i, v.end(), s.begin(),
                                       s.end());
      };
      bool operator()(string s, long long i) const {
        return lexicographical_compare(s.begin(), s.end(), v.begin() + i,
                                       v.end());
      };
    } cmp{v};
    auto it = lower_bound(sa.begin(), sa.end(), xv, cmp);
    if (it != sa.end()) prf[it - sa.begin()]++;
    it = upper_bound(sa.begin(), sa.end(), xv + char(127), cmp);
    if (it != sa.end()) prf[it - sa.begin()]--;
  }
  for (long long i = 1; i < n; i++) prf[i] += prf[i - 1];
  return prf;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ;
  string v;
  cin >> v;
  long long xn;
  cin >> xn;
  pv.resize(xn), rpv.resize(xn);
  for (long long i = 0; i < xn; i++)
    cin >> pv[i], rpv[i] = string(pv[i].rbegin(), pv[i].rend());
  long long n = v.length();
  string rv = string(v.rbegin(), v.rend());
  vector<long long> sa1 = SA(n, v), sa2 = SA(n, rv);
  vector<long long> s1 = bld(v, sa1, pv), s2 = bld(rv, sa2, rpv);
  vector<long long> r1 = RNK(n, sa1), r2 = RNK(n, sa2);
  long long sum = 0;
  reverse(r2.begin(), r2.end());
  for (long long i = 1; i < n; i++) sum += s2[r2[i - 1]] * s1[r1[i]];
  cout << sum << '\n';
}

```