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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
struct suffix_array {
  int n;
  vector<vector<int>> p;
  vector<int> idx;
  suffix_array(vector<int> s) : n(int((s).size())), p(1, s) {
    for (int k = 1, step = 1; step / 2 < n; k++, step *= 2) {
      vector<pair<pair<int, int>, int>> v(n);
      for (int i = (0); i < (n); i++)
        v[i] = {{p[k - 1][i], i + step < n ? p[k - 1][i + step] : -oo}, i};
      sort(begin(v), end(v));
      vector<int> q(n);
      for (int j = (1); j < (n); j++)
        q[v[j].second] = v[j].first == v[j - 1].first ? q[v[j - 1].second] : j;
      p.push_back(q);
    }
    idx.resize(n);
    for (int i = (0); i < (n); i++) idx[p[int((p).size()) - 1][i]] = i;
  }
  int lcp(int x, int y) {
    if (x == y) return int((idx).size()) - x;
    int res = 0;
    for (int k = (int((p).size())) - 1; k >= (0); k--) {
      if (max(x, y) >= n) break;
      if (p[k][x] == p[k][y]) x += 1 << k, y += 1 << k, res += 1 << k;
    }
    return res;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string t;
  cin >> t;
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = (0); i < (n); i++) cin >> s[i];
  vector<vector<int>> res(2, vector<int>(int((t).size())));
  for (int dir = (0); dir < (2); dir++) {
    vector<int> seq, start(n);
    for (char c : t) seq.push_back(c);
    seq.push_back(1);
    for (int i = (0); i < (n); i++) {
      start[i] = int((seq).size());
      for (char c : s[i]) seq.push_back(c);
      seq.push_back(-i);
    }
    suffix_array S(seq);
    vector<pair<int, int>> ev;
    for (int i = (0); i < (n); i++) {
      int x = start[i];
      int len = int((s[i]).size());
      int jmin = S.p.back()[x];
      ev.emplace_back(jmin, 1);
      int jmax = int((seq).size());
      while (jmax - jmin > 1) {
        int j = (jmin + jmax) / 2;
        int y = S.idx[j];
        if (S.lcp(x, y) < len)
          jmax = j;
        else
          jmin = j;
      }
      ev.emplace_back(jmax, -1);
    }
    sort(begin(ev), end(ev));
    int j = 0, cnt = 0;
    for (int i = (0); i < (int((seq).size())); i++) {
      while (j < int((ev).size()) && ev[j].first == i) {
        cnt += ev[j++].second;
      }
      if (S.idx[i] < int((t).size())) res[dir][S.idx[i]] = cnt;
    }
    reverse(begin(t), end(t));
    for (int i = (0); i < (n); i++) reverse(begin(s[i]), end(s[i]));
  }
  reverse(begin(res[1]), end(res[1]));
  for (int dir = (0); dir < (2); dir++)
    for (int i = (0); i < (int((t).size())); i++) {
    }
  long long ans = 0;
  for (int i = (1); i < (int((t).size())); i++)
    ans += res[0][i] * 1LL * res[1][i - 1];
  cout << ans << endl;
}