#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
char tmpread[N];
int n, a[N], b[N];
string s;
string arr[N];
int len;
string A;
int idx[N + N + N];
int mxorder = 0;
vector<int> suf, order, tmporder;
vector<int> lcp;
int frq[N + N + N], sum[N + N + N], tmpsort[N + N + N];
multiset<int> st;
inline bool equal(int i, int j) {
  return (tmporder[i] == tmporder[j] && tmporder[i + len] == tmporder[j + len]);
}
void radix_sort() {
  for (int i = 0; i <= mxorder; i++) frq[i] = sum[i] = 0;
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] + len >= (int)suf.size())
      frq[0]++;
    else
      frq[order[suf[i] + len]]++;
  }
  for (int i = 0; i <= mxorder; i++) {
    sum[i] = frq[i] + (i > 0 ? sum[i - 1] : 0);
  }
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] + len >= (int)suf.size()) {
      tmpsort[sum[0] - frq[0]] = suf[i];
      frq[0]--;
    } else {
      tmpsort[sum[order[suf[i] + len]] - frq[order[suf[i] + len]]] = suf[i];
      frq[order[suf[i] + len]]--;
    }
  }
  for (int i = 0; i < (int)suf.size(); i++) suf[i] = tmpsort[i];
  for (int i = 0; i <= mxorder; i++) frq[i] = sum[i] = 0;
  for (int i = 0; i < (int)suf.size(); i++) {
    frq[order[suf[i]]]++;
  }
  for (int i = 0; i <= mxorder; i++) {
    sum[i] = frq[i] + (i > 0 ? sum[i - 1] : 0);
  }
  for (int i = 0; i < (int)suf.size(); i++) {
    tmpsort[sum[order[suf[i]]] - frq[order[suf[i]]]] = suf[i];
    frq[order[suf[i]]]--;
  }
  for (int i = 0; i < (int)suf.size(); i++) suf[i] = tmpsort[i];
}
void build() {
  suf.clear();
  order.clear();
  tmporder.clear();
  suf.resize((int)A.size() + 1);
  order.resize((int)A.size() + 1);
  tmporder.resize((int)A.size() + 1);
  for (int i = 0; i <= (int)A.size(); i++) {
    suf[i] = i;
    order[i] = A[i];
    mxorder = max(mxorder, (int)A[i]);
  }
  for (len = 1; len < (int)suf.size(); len *= 2) {
    radix_sort();
    for (int i = 0; i < (int)suf.size(); i++) tmporder[i] = order[i];
    order[suf[0]] = 0;
    for (int i = 1; i < (int)suf.size(); i++) {
      order[suf[i]] = order[suf[i - 1]];
      if (!equal(suf[i], suf[i - 1])) order[suf[i]]++;
    }
    mxorder = order[suf.back()];
    if (mxorder == (int)A.size()) break;
  }
  suf.erase(suf.begin());
  for (int i = 0; i < (int)suf.size(); i++) {
    order[i]--;
  }
}
void build_lcp() {
  lcp.clear();
  lcp.resize((int)A.size());
  int k = 0, j;
  for (int i = 0; i < (int)A.size(); i++) {
    j = order[i] + 1;
    if (j == (int)suf.size()) {
      k = 0;
      continue;
    }
    j = suf[j];
    while (A[i + k] == A[j + k]) k++;
    lcp[i] = k;
    k--;
    k = max(k, 0);
  }
}
int main() {
  memset(idx, -1, sizeof(idx));
  scanf("%s", tmpread);
  s = (string)tmpread;
  A = s;
  A += 'Y';
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", tmpread);
    arr[i] = (string)tmpread;
    idx[(int)A.size()] = (int)arr[i].size();
    A += arr[i];
    A += 'X';
  }
  build();
  build_lcp();
  multiset<int>::iterator it;
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] < (int)s.size()) {
      a[suf[i]] = (int)st.size();
    } else if (idx[suf[i]] != -1) {
      st.insert(idx[suf[i]]);
    }
    while ((int)st.size() > 0) {
      it = st.end();
      it--;
      if (*it > lcp[suf[i]]) {
        st.erase(it);
        continue;
      }
      break;
    }
  }
  A.clear();
  reverse(s.begin(), s.end());
  st.clear();
  A = s;
  A += 'Y';
  for (int i = 0; i < n; i++) {
    reverse(arr[i].begin(), arr[i].end());
    A += arr[i];
    A += 'X';
  }
  build();
  build_lcp();
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] < (int)s.size()) {
      b[(int)s.size() - suf[i] - 1] = (int)st.size();
    } else if (idx[suf[i]] != -1) {
      st.insert(idx[suf[i]]);
    }
    while ((int)st.size() > 0) {
      it = st.end();
      it--;
      if (*it > lcp[suf[i]]) {
        st.erase(it);
        continue;
      }
      break;
    }
  }
  long long ans = 0;
  for (int i = 1; i < (int)s.size(); i++) {
    ans += (long long)b[i - 1] * a[i];
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
const int N = 200010;
char tmpread[N];
int n, a[N], b[N];
string s;
string arr[N];
int len;
string A;
int idx[N + N + N];
int mxorder = 0;
vector<int> suf, order, tmporder;
vector<int> lcp;
int frq[N + N + N], sum[N + N + N], tmpsort[N + N + N];
multiset<int> st;
inline bool equal(int i, int j) {
  return (tmporder[i] == tmporder[j] && tmporder[i + len] == tmporder[j + len]);
}
void radix_sort() {
  for (int i = 0; i <= mxorder; i++) frq[i] = sum[i] = 0;
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] + len >= (int)suf.size())
      frq[0]++;
    else
      frq[order[suf[i] + len]]++;
  }
  for (int i = 0; i <= mxorder; i++) {
    sum[i] = frq[i] + (i > 0 ? sum[i - 1] : 0);
  }
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] + len >= (int)suf.size()) {
      tmpsort[sum[0] - frq[0]] = suf[i];
      frq[0]--;
    } else {
      tmpsort[sum[order[suf[i] + len]] - frq[order[suf[i] + len]]] = suf[i];
      frq[order[suf[i] + len]]--;
    }
  }
  for (int i = 0; i < (int)suf.size(); i++) suf[i] = tmpsort[i];
  for (int i = 0; i <= mxorder; i++) frq[i] = sum[i] = 0;
  for (int i = 0; i < (int)suf.size(); i++) {
    frq[order[suf[i]]]++;
  }
  for (int i = 0; i <= mxorder; i++) {
    sum[i] = frq[i] + (i > 0 ? sum[i - 1] : 0);
  }
  for (int i = 0; i < (int)suf.size(); i++) {
    tmpsort[sum[order[suf[i]]] - frq[order[suf[i]]]] = suf[i];
    frq[order[suf[i]]]--;
  }
  for (int i = 0; i < (int)suf.size(); i++) suf[i] = tmpsort[i];
}
void build() {
  suf.clear();
  order.clear();
  tmporder.clear();
  suf.resize((int)A.size() + 1);
  order.resize((int)A.size() + 1);
  tmporder.resize((int)A.size() + 1);
  for (int i = 0; i <= (int)A.size(); i++) {
    suf[i] = i;
    order[i] = A[i];
    mxorder = max(mxorder, (int)A[i]);
  }
  for (len = 1; len < (int)suf.size(); len *= 2) {
    radix_sort();
    for (int i = 0; i < (int)suf.size(); i++) tmporder[i] = order[i];
    order[suf[0]] = 0;
    for (int i = 1; i < (int)suf.size(); i++) {
      order[suf[i]] = order[suf[i - 1]];
      if (!equal(suf[i], suf[i - 1])) order[suf[i]]++;
    }
    mxorder = order[suf.back()];
    if (mxorder == (int)A.size()) break;
  }
  suf.erase(suf.begin());
  for (int i = 0; i < (int)suf.size(); i++) {
    order[i]--;
  }
}
void build_lcp() {
  lcp.clear();
  lcp.resize((int)A.size());
  int k = 0, j;
  for (int i = 0; i < (int)A.size(); i++) {
    j = order[i] + 1;
    if (j == (int)suf.size()) {
      k = 0;
      continue;
    }
    j = suf[j];
    while (A[i + k] == A[j + k]) k++;
    lcp[i] = k;
    k--;
    k = max(k, 0);
  }
}
int main() {
  memset(idx, -1, sizeof(idx));
  scanf("%s", tmpread);
  s = (string)tmpread;
  A = s;
  A += 'Y';
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", tmpread);
    arr[i] = (string)tmpread;
    idx[(int)A.size()] = (int)arr[i].size();
    A += arr[i];
    A += 'X';
  }
  build();
  build_lcp();
  multiset<int>::iterator it;
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] < (int)s.size()) {
      a[suf[i]] = (int)st.size();
    } else if (idx[suf[i]] != -1) {
      st.insert(idx[suf[i]]);
    }
    while ((int)st.size() > 0) {
      it = st.end();
      it--;
      if (*it > lcp[suf[i]]) {
        st.erase(it);
        continue;
      }
      break;
    }
  }
  A.clear();
  reverse(s.begin(), s.end());
  st.clear();
  A = s;
  A += 'Y';
  for (int i = 0; i < n; i++) {
    reverse(arr[i].begin(), arr[i].end());
    A += arr[i];
    A += 'X';
  }
  build();
  build_lcp();
  for (int i = 0; i < (int)suf.size(); i++) {
    if (suf[i] < (int)s.size()) {
      b[(int)s.size() - suf[i] - 1] = (int)st.size();
    } else if (idx[suf[i]] != -1) {
      st.insert(idx[suf[i]]);
    }
    while ((int)st.size() > 0) {
      it = st.end();
      it--;
      if (*it > lcp[suf[i]]) {
        st.erase(it);
        continue;
      }
      break;
    }
  }
  long long ans = 0;
  for (int i = 1; i < (int)s.size(); i++) {
    ans += (long long)b[i - 1] * a[i];
  }
  cout << ans << endl;
  return 0;
}

```