#include <bits/stdc++.h>
using namespace std;
vector<int> sort_cyclic_shifts(const string& s, const int ALPHA = 256) {
  int n = (int)s.size();
  vector<int> cnt(max(ALPHA, n), 0);
  vector<int> p(n), g(n);
  int numgroups;
  for (auto c : s) ++cnt[c];
  for (int i = 1; i < ALPHA; ++i) cnt[i] += cnt[i - 1];
  for (int i = n - 1; i >= 0; --i) p[--cnt[s[i]]] = i;
  numgroups = 1;
  g[p[0]] = 0;
  for (int i = 1; i < n; ++i) {
    if (s[p[i]] != s[p[i - 1]]) ++numgroups;
    g[p[i]] = numgroups - 1;
  }
  vector<int> pn(n), gn(n);
  for (int h = 0; (1 << h) < n; ++h) {
    const int H = 1 << h;
    for (int i = 0; i < n; ++i) {
      pn[i] = p[i] - H;
      if (pn[i] < 0) pn[i] += n;
    }
    fill(cnt.begin(), cnt.begin() + numgroups, 0);
    for (int i = 0; i < n; ++i) ++cnt[g[i]];
    for (int i = 1; i < numgroups; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) p[--cnt[g[pn[i]]]] = pn[i];
    numgroups = 1;
    gn[p[0]] = 0;
    pair<int, int> prev{g[p[0]], g[(p[0] + H) % n]}, cur;
    for (int i = 1; i < n; ++i) {
      cur = {g[p[i]], g[(p[i] + H) % n]};
      if (cur != prev) ++numgroups;
      gn[p[i]] = numgroups - 1;
      prev = cur;
    }
    g.swap(gn);
  }
  return p;
}
vector<int> compute_suffix_array(string s, char sentinel = '$') {
  s += sentinel;
  auto p = sort_cyclic_shifts(s);
  p.erase(p.begin());
  return p;
}
int fixed_length_suffcmp(int i, const string& s, const string& w) {
  for (int j = 0; j < (int)min(w.size(), s.size() - i); ++j) {
    if (s[i + j] < w[j])
      return -1;
    else if (s[i + j] > w[j])
      return 1;
  }
  if (w.size() > s.size() - i) return -1;
  return 0;
}
int lowerbound(const string& t, const vector<int>& suffarr, const string& w) {
  int n = (int)t.size();
  if (fixed_length_suffcmp(suffarr[n - 1], t, w) < 0) return n;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (fixed_length_suffcmp(suffarr[mid], t, w) < 0) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}
int upperbound(const string& t, const vector<int>& suffarr, const string& w) {
  int n = (int)t.size();
  if (fixed_length_suffcmp(suffarr[n - 1], t, w) <= 0) return n;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (fixed_length_suffcmp(suffarr[mid], t, w) <= 0) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}
vector<int> prefcnt(const string& t, const vector<string>& s) {
  int n = (int)t.size();
  auto suffarr = compute_suffix_array(t);
  vector<int> p(t.size(), 0);
  for (const string& w : s) {
    int lbound = lowerbound(t, suffarr, w);
    int ubound = upperbound(t, suffarr, w);
    if (lbound < n) ++p[lbound];
    if (ubound < n) --p[ubound];
  }
  for (int i = 1; i < n; ++i) p[i] += p[i - 1];
  vector<int> cnt(n, 0);
  for (int i = 0; i < n; ++i) {
    cnt[suffarr[i]] = p[i];
  }
  return cnt;
}
int main() {
  string t;
  cin >> t;
  int n;
  cin >> n;
  vector<string> s(n);
  for (auto& w : s) {
    cin >> w;
  }
  auto start = prefcnt(t, s);
  reverse(t.begin(), t.end());
  for (auto& w : s) {
    reverse(w.begin(), w.end());
  }
  auto end = prefcnt(t, s);
  reverse(end.begin(), end.end());
  long long ans = 0;
  for (int i = 1; i < (int)t.size(); ++i) {
    ans += 1LL * end[i - 1] * start[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;
vector<int> sort_cyclic_shifts(const string& s, const int ALPHA = 256) {
  int n = (int)s.size();
  vector<int> cnt(max(ALPHA, n), 0);
  vector<int> p(n), g(n);
  int numgroups;
  for (auto c : s) ++cnt[c];
  for (int i = 1; i < ALPHA; ++i) cnt[i] += cnt[i - 1];
  for (int i = n - 1; i >= 0; --i) p[--cnt[s[i]]] = i;
  numgroups = 1;
  g[p[0]] = 0;
  for (int i = 1; i < n; ++i) {
    if (s[p[i]] != s[p[i - 1]]) ++numgroups;
    g[p[i]] = numgroups - 1;
  }
  vector<int> pn(n), gn(n);
  for (int h = 0; (1 << h) < n; ++h) {
    const int H = 1 << h;
    for (int i = 0; i < n; ++i) {
      pn[i] = p[i] - H;
      if (pn[i] < 0) pn[i] += n;
    }
    fill(cnt.begin(), cnt.begin() + numgroups, 0);
    for (int i = 0; i < n; ++i) ++cnt[g[i]];
    for (int i = 1; i < numgroups; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) p[--cnt[g[pn[i]]]] = pn[i];
    numgroups = 1;
    gn[p[0]] = 0;
    pair<int, int> prev{g[p[0]], g[(p[0] + H) % n]}, cur;
    for (int i = 1; i < n; ++i) {
      cur = {g[p[i]], g[(p[i] + H) % n]};
      if (cur != prev) ++numgroups;
      gn[p[i]] = numgroups - 1;
      prev = cur;
    }
    g.swap(gn);
  }
  return p;
}
vector<int> compute_suffix_array(string s, char sentinel = '$') {
  s += sentinel;
  auto p = sort_cyclic_shifts(s);
  p.erase(p.begin());
  return p;
}
int fixed_length_suffcmp(int i, const string& s, const string& w) {
  for (int j = 0; j < (int)min(w.size(), s.size() - i); ++j) {
    if (s[i + j] < w[j])
      return -1;
    else if (s[i + j] > w[j])
      return 1;
  }
  if (w.size() > s.size() - i) return -1;
  return 0;
}
int lowerbound(const string& t, const vector<int>& suffarr, const string& w) {
  int n = (int)t.size();
  if (fixed_length_suffcmp(suffarr[n - 1], t, w) < 0) return n;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (fixed_length_suffcmp(suffarr[mid], t, w) < 0) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}
int upperbound(const string& t, const vector<int>& suffarr, const string& w) {
  int n = (int)t.size();
  if (fixed_length_suffcmp(suffarr[n - 1], t, w) <= 0) return n;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (fixed_length_suffcmp(suffarr[mid], t, w) <= 0) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}
vector<int> prefcnt(const string& t, const vector<string>& s) {
  int n = (int)t.size();
  auto suffarr = compute_suffix_array(t);
  vector<int> p(t.size(), 0);
  for (const string& w : s) {
    int lbound = lowerbound(t, suffarr, w);
    int ubound = upperbound(t, suffarr, w);
    if (lbound < n) ++p[lbound];
    if (ubound < n) --p[ubound];
  }
  for (int i = 1; i < n; ++i) p[i] += p[i - 1];
  vector<int> cnt(n, 0);
  for (int i = 0; i < n; ++i) {
    cnt[suffarr[i]] = p[i];
  }
  return cnt;
}
int main() {
  string t;
  cin >> t;
  int n;
  cin >> n;
  vector<string> s(n);
  for (auto& w : s) {
    cin >> w;
  }
  auto start = prefcnt(t, s);
  reverse(t.begin(), t.end());
  for (auto& w : s) {
    reverse(w.begin(), w.end());
  }
  auto end = prefcnt(t, s);
  reverse(end.begin(), end.end());
  long long ans = 0;
  for (int i = 1; i < (int)t.size(); ++i) {
    ans += 1LL * end[i - 1] * start[i];
  }
  cout << ans << "\n";
}

```