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 long long inf = 1e15;
const long long MOD = 998244353;
struct th {
  int first, second, ind;
  friend bool operator<(const th& a, const th& b) {
    if (a.first == b.first) {
      return (a.second == b.second ? a.ind < b.ind : a.second < b.second);
    }
    return a.first < b.first;
  }
};
void realQuickSort(vector<th>& a) {
  int n = a.size();
  vector<int> cnt(n);
  for (const auto& i : a) {
    ++cnt[i.second];
  }
  vector<int> ind(n, 0);
  for (int i = 1; i < n; ++i) {
    ind[i] = ind[i - 1] + cnt[i - 1];
  }
  auto temp = a;
  for (int i = 0; i < n; ++i) {
    temp[ind[a[i].second]] = a[i];
    ++ind[a[i].second];
  }
  cnt.assign(n, 0);
  for (const auto& i : temp) {
    ++cnt[i.first];
  }
  ind[0] = 0;
  for (int i = 1; i < n; ++i) {
    ind[i] = ind[i - 1] + cnt[i - 1];
  }
  for (int i = 0; i < n; ++i) {
    a[ind[temp[i].first]] = temp[i];
    ++ind[temp[i].first];
  }
}
vector<int> SufArr(string s) {
  int n = s.size();
  vector<pair<char, int>> temp(n);
  for (int i = 0; i < n; ++i) {
    temp[i] = {s[i], i};
  }
  sort(temp.begin(), temp.end());
  vector<int> cl(n);
  cl[temp[0].second] = 0;
  for (int i = 1; i < n; ++i) {
    cl[temp[i].second] = cl[temp[i - 1].second];
    if (temp[i].first != temp[i - 1].first) ++cl[temp[i].second];
  }
  vector<th> a(n);
  int k = 0;
  while ((1 << k) < n) {
    for (int i = 0; i < n; ++i) {
      a[i].first = cl[i];
      a[i].second = cl[(i + (1 << k)) % n];
      a[i].ind = i;
    }
    realQuickSort(a);
    cl[a[0].ind] = 0;
    for (int i = 1; i < n; ++i) {
      cl[a[i].ind] = cl[a[i - 1].ind];
      if (a[i].first != a[i - 1].first || a[i].second != a[i - 1].second)
        ++cl[a[i].ind];
    }
    ++k;
  }
  vector<int> pos(n);
  for (int i = 0; i < n; ++i) {
    pos[i] = a[i].ind;
  }
  return pos;
}
class segment_tree {
  vector<long long> tree;
  vector<long long> modify;
  int len;
  const long long inff = 1e15;
  void build(const vector<long long>& a) {
    len = 1;
    while (len <= (int)a.size()) {
      len *= 2;
    }
    len *= 2;
    tree.resize(len, -inff);
    modify.resize(len, 0);
    for (int i = len / 2; i < (int)a.size() + len / 2; ++i) {
      tree[i] = a[i - len / 2];
    }
    for (int i = len / 2 - 1; i > 0; i--) {
      tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
  }
  void mod(int v, long long sz) {
    tree[v] += modify[v] * sz;
    if (2 * v + 1 < len) {
      modify[v * 2] += modify[v];
      modify[v * 2 + 1] += modify[v];
    }
    modify[v] = 0;
  }
  long long pGet(int l, int r, int v, int tl, int tr) {
    if (l > r) return -inff;
    mod(v, tr - tl);
    if (l == tl && r == tr) {
      return tree[v];
    }
    if (r <= (tl + tr) / 2) {
      return pGet(l, r, 2 * v, tl, (tl + tr) / 2);
    }
    if (l >= (tl + tr) / 2) {
      return pGet(l, r, 2 * v + 1, (tl + tr) / 2, tr);
    }
    return (pGet(l, (tl + tr) / 2, 2 * v, tl, (tl + tr) / 2) +
            pGet((tl + tr) / 2, r, 2 * v + 1, (tl + tr) / 2, tr));
  }
  void pUpdate(int l, int r, int v, int tl, int tr, long long add) {
    if (l > r) return;
    mod(v, tr - tl);
    if (l == tl && r == tr) {
      modify[v] += add;
      mod(v, tr - tl);
      return;
    } else if (r <= (tl + tr) / 2) {
      pUpdate(l, r, 2 * v, tl, (tl + tr) / 2, add);
    } else if (l >= (tl + tr) / 2) {
      pUpdate(l, r, 2 * v + 1, (tl + tr) / 2, tr, add);
    } else {
      pUpdate(l, (tl + tr) / 2, 2 * v, tl, (tl + tr) / 2, add),
          pUpdate((tl + tr) / 2, r, 2 * v + 1, (tl + tr) / 2, tr, add);
    }
    if (2 * v + 1 < len) {
      mod(v * 2, (tr - tl) / 2);
      mod(v * 2 + 1, (tr - tl) / 2);
      tree[v] = (tree[v * 2] + tree[v * 2 + 1]);
    }
  }

 public:
  segment_tree(const vector<long long>& a) { build(a); }
  void update(int ind, long long val) {
    int v = len / 2 + ind;
    tree[v] = val;
    while (v != 1) {
      int v2 = (v % 2 ? v - 1 : v + 1);
      if (v < v2)
        tree[v / 2] = (tree[v] + tree[v2]);
      else
        tree[v / 2] = (tree[v2] + tree[v]);
    }
  }
  long long get(int l, int r) { return pGet(l, r, 1, 0, tree.size() / 2); }
  void update(int l, int r, long long add) {
    pUpdate(l, r, 1, 0, tree.size() / 2, add);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << setprecision(30);
  string t;
  cin >> t;
  t += '!';
  int n;
  cin >> n;
  vector<string> a(n);
  for (auto& i : a) {
    cin >> i;
  }
  auto p = SufArr(t);
  vector<long long> arr(t.size());
  segment_tree startTree(arr);
  auto s = t + t;
  for (auto& temp : a) {
    int l = 0, r = p.size();
    --r;
    while (l < r) {
      int mid = (l + r) / 2;
      int count = 0;
      for (int i = 0; i < temp.size(); ++i) {
        count = temp[i] - s[p[mid] + i];
        if (count != 0) break;
      }
      if (count < 0) {
        r = mid - 1;
      } else if (count == 0) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    int f = l;
    int count = 0;
    for (int i = 0; i < temp.size(); ++i) {
      count = temp[i] - s[p[f] + i];
      if (count != 0) break;
    }
    if (count != 0) ++f;
    l = 0, r = p.size();
    --r;
    while (l < r) {
      int mid = (l + r) / 2;
      int count = 0;
      for (int i = 0; i < temp.size(); ++i) {
        count = temp[i] - s[p[mid] + i];
        if (count != 0) break;
      }
      if (count >= 0) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    count = 0;
    for (int i = 0; i < temp.size(); ++i) {
      count = temp[i] - s[p[r] + i];
      if (count != 0) break;
    }
    if (count == 0) ++r;
    if (r - f > 0) startTree.update(f, r, 1);
  }
  for (int i = 0; i < arr.size(); ++i) {
    arr[i] = startTree.get(i, i + 1);
  }
  vector<long long> start(arr.size());
  for (int i = 0; i < arr.size(); ++i) {
    start[p[i]] = arr[i];
  }
  arr.assign(arr.size(), 0);
  segment_tree endTree(arr);
  t.pop_back();
  reverse(t.begin(), t.end());
  t += '!';
  s = t + t;
  p = SufArr(t);
  for (auto& temp : a) {
    reverse(temp.begin(), temp.end());
    int l = 0, r = p.size();
    --r;
    while (l < r) {
      int mid = (l + r) / 2;
      int count = 0;
      for (int i = 0; i < temp.size(); ++i) {
        count = temp[i] - s[p[mid] + i];
        if (count != 0) break;
      }
      if (count < 0) {
        r = mid - 1;
      } else if (count == 0) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    int f = l;
    int count = 0;
    for (int i = 0; i < temp.size(); ++i) {
      count = temp[i] - s[p[f] + i];
      if (count != 0) break;
    }
    if (count != 0) ++f;
    l = 0, r = p.size();
    --r;
    while (l < r) {
      int mid = (l + r) / 2;
      int count = 0;
      for (int i = 0; i < temp.size(); ++i) {
        count = temp[i] - s[p[mid] + i];
        if (count != 0) break;
      }
      if (count >= 0) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    count = 0;
    for (int i = 0; i < temp.size(); ++i) {
      count = temp[i] - s[p[r] + i];
      if (count != 0) break;
    }
    if (count == 0) ++r;
    if (r - f > 0) endTree.update(f, r, 1);
  }
  for (int i = 0; i < arr.size(); ++i) {
    arr[i] = endTree.get(i, i + 1);
  }
  vector<long long> end(arr.size());
  for (int i = 0; i < arr.size(); ++i) {
    end[p[i]] = arr[i];
  }
  end.pop_back();
  reverse(end.begin(), end.end());
  long long ans = 0;
  for (int i = 0; i < (int)start.size() - 1; ++i) {
    ans += end[i] * start[i + 1];
  }
  cout << ans;
  return 0;
}