#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int maxm = 128;
const int maxlog = 20;
struct SuffixArray {
  int m, n, rk[maxn], c[maxn], sa[maxn], t2[maxn], t[maxn], ht[maxn];
  char s[maxn];
  void build_sa() {
    n = strlen(s);
    m = maxm;
    int i, *x = t, *y = t2, p = 0;
    for (i = 0; i < m; i++) c[i] = 0;
    for (i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (i = 1; i < m; i++) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n && p < n; k <<= 1) {
      p = 0;
      for (i = n - k; i < n; i++) y[p++] = i;
      for (i = 0; i < n; i++)
        if (sa[i] >= k) y[p++] = sa[i] - k;
      for (i = 0; i < m; i++) c[i] = 0;
      for (i = 0; i < n; i++) c[x[y[i]]]++;
      for (i = 1; i < m; i++) c[i] += c[i - 1];
      for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
      swap(x, y);
      p = 1;
      x[sa[0]] = 0;
      for (i = 1; i < n; i++)
        x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && sa[i - 1] + k < n &&
                           sa[i] + k < n && y[sa[i - 1] + k] == y[sa[i] + k]
                       ? p - 1
                       : p++;
      m = p;
    }
  }
  void getHeight() {
    int i, j, k = 0;
    for (i = 0; i < n; i++) rk[sa[i]] = i;
    for (i = 0; i < n; i++) {
      if (!rk[i]) continue;
      if (k) --k;
      j = sa[rk[i] - 1];
      while (j + k < n && i + k < n && s[i + k] == s[j + k]) ++k;
      ht[rk[i]] = k;
    }
  }
  int d[maxn][maxlog], mm[maxn];
  void RMQ_init() {
    mm[0] = -1;
    for (int i = 1; i < n; i++) mm[i] = i & i - 1 ? mm[i - 1] : mm[i - 1] + 1;
    for (int i = 1; i < n; i++) d[i][0] = i;
    for (int j = 1; 1 << j < n; j++)
      for (int i = 1; i + (1 << j) - 1 < n; j++)
        if (ht[d[i][j - 1]] < ht[d[i + (1 << j - 1)][j - 1]])
          d[i][j] = d[i][j - 1];
        else
          d[i][j] = d[i + (1 << j - 1)][j - 1];
  }
  int LCP(int L, int R) {
    if (L == R) return n - L;
    L = rk[L], R = rk[R];
    if (L > R) swap(L, R);
    L++;
    int &t = mm[R - L + 1];
    return min(ht[d[L][t]], ht[d[R - (1 << t) + 1][t]]);
  }
  int f_strncmp(char *P, char *S, int &pos, int m) {
    for (; pos < m && P[pos] == S[pos]; pos++)
      ;
    if (pos == m) return 0;
    return P[pos] > S[pos] ? 1 : -1;
  }
  int fast_lower_bound(char *P) {
    int L = 0, R = n, M, r, max_match = 0, lst = 0, pos, m = strlen(P);
    while (L < R) {
      int M = L + R >> 1;
      pos = min(max_match, LCP(sa[M], sa[lst]));
      r = f_strncmp(P, s + sa[M], pos, m);
      if (pos > max_match) max_match = pos, lst = M;
      if (r > 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int fast_upper_bound(char *P) {
    int L = 0, R = n, M, r, max_match = 0, lst = 0, pos, m = strlen(P);
    while (L < R) {
      int M = L + R >> 1;
      pos = min(max_match, LCP(sa[M], sa[lst]));
      r = f_strncmp(P, s + sa[M], pos, m);
      if (pos > max_match) max_match = pos, lst = M;
      if (r >= 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int slow_lower_bound(char *P) {
    int L = 0, R = n, M, r, m = strlen(P);
    while (L < R) {
      M = L + R >> 1;
      r = strncmp(P, s + sa[M], m);
      if (r > 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int slow_upper_bound(char *P) {
    int L = 0, R = n, M, r, m = strlen(P);
    while (L < R) {
      M = L + R >> 1;
      r = strncmp(P, s + sa[M], m);
      if (r >= 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
} A, B;
char s[200005], ss[200005];
int n, m, al[200004], bl[200004];
long long ans;
int main() {
  scanf("%s", A.s);
  n = strlen(A.s);
  for (int i = 0; i < n; i++) B.s[n - i - 1] = A.s[i];
  A.build_sa();
  B.build_sa();
  A.getHeight();
  B.getHeight();
  A.RMQ_init();
  B.RMQ_init();
  scanf("%d", &m);
  for (int i = 1, p, q, h; i <= m; i++) {
    scanf("%s", s);
    h = strlen(s);
    for (int j = 0; j < h; j++) ss[h - j - 1] = s[j];
    ss[h] = '\0';
    p = A.fast_lower_bound(s);
    q = A.fast_upper_bound(s);
    al[p]++, al[q]--;
    p = B.fast_lower_bound(ss);
    q = B.fast_upper_bound(ss);
    bl[p]++, bl[q]--;
  }
  for (int i = 1; i < n; i++) al[i] += al[i - 1], bl[i] += bl[i - 1];
  for (int i = 0; i < n; i++)
    if (A.sa[i]) ans += (long long)al[i] * bl[B.rk[n - A.sa[i]]];
  printf("%lld", ans);
  return 0;
}

### Prompt

Please create a solution in cpp 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>
using namespace std;
const int maxn = 200005;
const int maxm = 128;
const int maxlog = 20;
struct SuffixArray {
  int m, n, rk[maxn], c[maxn], sa[maxn], t2[maxn], t[maxn], ht[maxn];
  char s[maxn];
  void build_sa() {
    n = strlen(s);
    m = maxm;
    int i, *x = t, *y = t2, p = 0;
    for (i = 0; i < m; i++) c[i] = 0;
    for (i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (i = 1; i < m; i++) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n && p < n; k <<= 1) {
      p = 0;
      for (i = n - k; i < n; i++) y[p++] = i;
      for (i = 0; i < n; i++)
        if (sa[i] >= k) y[p++] = sa[i] - k;
      for (i = 0; i < m; i++) c[i] = 0;
      for (i = 0; i < n; i++) c[x[y[i]]]++;
      for (i = 1; i < m; i++) c[i] += c[i - 1];
      for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
      swap(x, y);
      p = 1;
      x[sa[0]] = 0;
      for (i = 1; i < n; i++)
        x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && sa[i - 1] + k < n &&
                           sa[i] + k < n && y[sa[i - 1] + k] == y[sa[i] + k]
                       ? p - 1
                       : p++;
      m = p;
    }
  }
  void getHeight() {
    int i, j, k = 0;
    for (i = 0; i < n; i++) rk[sa[i]] = i;
    for (i = 0; i < n; i++) {
      if (!rk[i]) continue;
      if (k) --k;
      j = sa[rk[i] - 1];
      while (j + k < n && i + k < n && s[i + k] == s[j + k]) ++k;
      ht[rk[i]] = k;
    }
  }
  int d[maxn][maxlog], mm[maxn];
  void RMQ_init() {
    mm[0] = -1;
    for (int i = 1; i < n; i++) mm[i] = i & i - 1 ? mm[i - 1] : mm[i - 1] + 1;
    for (int i = 1; i < n; i++) d[i][0] = i;
    for (int j = 1; 1 << j < n; j++)
      for (int i = 1; i + (1 << j) - 1 < n; j++)
        if (ht[d[i][j - 1]] < ht[d[i + (1 << j - 1)][j - 1]])
          d[i][j] = d[i][j - 1];
        else
          d[i][j] = d[i + (1 << j - 1)][j - 1];
  }
  int LCP(int L, int R) {
    if (L == R) return n - L;
    L = rk[L], R = rk[R];
    if (L > R) swap(L, R);
    L++;
    int &t = mm[R - L + 1];
    return min(ht[d[L][t]], ht[d[R - (1 << t) + 1][t]]);
  }
  int f_strncmp(char *P, char *S, int &pos, int m) {
    for (; pos < m && P[pos] == S[pos]; pos++)
      ;
    if (pos == m) return 0;
    return P[pos] > S[pos] ? 1 : -1;
  }
  int fast_lower_bound(char *P) {
    int L = 0, R = n, M, r, max_match = 0, lst = 0, pos, m = strlen(P);
    while (L < R) {
      int M = L + R >> 1;
      pos = min(max_match, LCP(sa[M], sa[lst]));
      r = f_strncmp(P, s + sa[M], pos, m);
      if (pos > max_match) max_match = pos, lst = M;
      if (r > 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int fast_upper_bound(char *P) {
    int L = 0, R = n, M, r, max_match = 0, lst = 0, pos, m = strlen(P);
    while (L < R) {
      int M = L + R >> 1;
      pos = min(max_match, LCP(sa[M], sa[lst]));
      r = f_strncmp(P, s + sa[M], pos, m);
      if (pos > max_match) max_match = pos, lst = M;
      if (r >= 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int slow_lower_bound(char *P) {
    int L = 0, R = n, M, r, m = strlen(P);
    while (L < R) {
      M = L + R >> 1;
      r = strncmp(P, s + sa[M], m);
      if (r > 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int slow_upper_bound(char *P) {
    int L = 0, R = n, M, r, m = strlen(P);
    while (L < R) {
      M = L + R >> 1;
      r = strncmp(P, s + sa[M], m);
      if (r >= 0)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
} A, B;
char s[200005], ss[200005];
int n, m, al[200004], bl[200004];
long long ans;
int main() {
  scanf("%s", A.s);
  n = strlen(A.s);
  for (int i = 0; i < n; i++) B.s[n - i - 1] = A.s[i];
  A.build_sa();
  B.build_sa();
  A.getHeight();
  B.getHeight();
  A.RMQ_init();
  B.RMQ_init();
  scanf("%d", &m);
  for (int i = 1, p, q, h; i <= m; i++) {
    scanf("%s", s);
    h = strlen(s);
    for (int j = 0; j < h; j++) ss[h - j - 1] = s[j];
    ss[h] = '\0';
    p = A.fast_lower_bound(s);
    q = A.fast_upper_bound(s);
    al[p]++, al[q]--;
    p = B.fast_lower_bound(ss);
    q = B.fast_upper_bound(ss);
    bl[p]++, bl[q]--;
  }
  for (int i = 1; i < n; i++) al[i] += al[i - 1], bl[i] += bl[i - 1];
  for (int i = 0; i < n; i++)
    if (A.sa[i]) ans += (long long)al[i] * bl[B.rk[n - A.sa[i]]];
  printf("%lld", ans);
  return 0;
}

```