#include <bits/stdc++.h>
template <typename T>
bool ckmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool ckmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
using namespace std;
const long long inf = (1ll << 60);
const double Pi = acos(-1);
const long long mod = 1e16 + 81;
const double eps = 1e-6;
inline int fpow(int a, int b = mod - 2, int p = mod) {
  a %= p;
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % p;
    a = 1ll * a * a % p;
    b >>= 1;
  }
  return res;
}
inline int read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
inline void write(int x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) {
  write(x);
  putchar('\n');
}
string str;
int t[222222];
int n, lent;
struct SAM {
  struct node {
    int len, nxt, son[26];
  } a[444444];
  int ans[444444], edp[444444], cnt[444444];
  int lst, tn;
  vector<int> e[444444];
  inline void init_SAM() { tn = lst = 1; }
  void extend_SAM(int c) {
    int cur = ++tn, p = lst;
    a[cur].len = a[p].len + 1;
    edp[cur] = a[p].len;
    for (; p && !a[p].son[c]; p = a[p].nxt) a[p].son[c] = cur;
    if (!p)
      a[cur].nxt = 1;
    else {
      int v = a[p].son[c];
      if (a[v].len == a[p].len + 1)
        a[cur].nxt = v;
      else {
        int x = ++tn;
        a[x] = a[v];
        a[x].len = a[p].len + 1;
        edp[x] = -1;
        for (; p && a[p].son[c] == v; p = a[p].nxt) a[p].son[c] = x;
        a[cur].nxt = a[v].nxt = x;
      }
    }
    lst = cur;
  }
  void solve(const string &s) {
    int p = 1, len = (int)s.size(), x;
    for (int i = (0), iE = (len - 1); i <= iE; i++) {
      x = s[i] - 'a';
      if (!a[p].son[x]) return;
      p = a[p].son[x];
    }
    ++cnt[p];
  }
  void dfs(int u) {
    if (~edp[u]) ans[edp[u]] = cnt[u];
    for (int v : e[u]) cnt[v] += cnt[u], dfs(v);
  }
  void mian() {
    for (int i = (2), iE = (tn); i <= iE; i++) e[a[i].nxt].push_back(i);
    dfs(1);
  }
} SAM1, SAM2;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  SAM1.init_SAM(), SAM2.init_SAM();
  cin >> str >> n;
  lent = str.size();
  for (int i = (0), iE = (lent - 1); i <= iE; i++) t[i] = str[i] - 'a';
  for (int i = (0), iE = (lent - 1); i <= iE; i++) SAM1.extend_SAM(t[i]);
  for (int i = (lent - 1), iE = (0); i >= iE; i--) SAM2.extend_SAM(t[i]);
  for (int i = (1), iE = (n); i <= iE; i++) {
    cin >> str;
    SAM1.solve(str);
    reverse(str.begin(), str.end());
    SAM2.solve(str);
  }
  SAM1.mian();
  SAM2.mian();
  long long ans = 0;
  for (int i = (0), iE = (lent - 2); i <= iE; i++)
    ans += 1ll * SAM1.ans[i] * SAM2.ans[lent - i - 2];
  cout << ans;
}

### Prompt

Your task is to create a cpp solution 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>
template <typename T>
bool ckmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool ckmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
using namespace std;
const long long inf = (1ll << 60);
const double Pi = acos(-1);
const long long mod = 1e16 + 81;
const double eps = 1e-6;
inline int fpow(int a, int b = mod - 2, int p = mod) {
  a %= p;
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % p;
    a = 1ll * a * a % p;
    b >>= 1;
  }
  return res;
}
inline int read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
inline void write(int x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) {
  write(x);
  putchar('\n');
}
string str;
int t[222222];
int n, lent;
struct SAM {
  struct node {
    int len, nxt, son[26];
  } a[444444];
  int ans[444444], edp[444444], cnt[444444];
  int lst, tn;
  vector<int> e[444444];
  inline void init_SAM() { tn = lst = 1; }
  void extend_SAM(int c) {
    int cur = ++tn, p = lst;
    a[cur].len = a[p].len + 1;
    edp[cur] = a[p].len;
    for (; p && !a[p].son[c]; p = a[p].nxt) a[p].son[c] = cur;
    if (!p)
      a[cur].nxt = 1;
    else {
      int v = a[p].son[c];
      if (a[v].len == a[p].len + 1)
        a[cur].nxt = v;
      else {
        int x = ++tn;
        a[x] = a[v];
        a[x].len = a[p].len + 1;
        edp[x] = -1;
        for (; p && a[p].son[c] == v; p = a[p].nxt) a[p].son[c] = x;
        a[cur].nxt = a[v].nxt = x;
      }
    }
    lst = cur;
  }
  void solve(const string &s) {
    int p = 1, len = (int)s.size(), x;
    for (int i = (0), iE = (len - 1); i <= iE; i++) {
      x = s[i] - 'a';
      if (!a[p].son[x]) return;
      p = a[p].son[x];
    }
    ++cnt[p];
  }
  void dfs(int u) {
    if (~edp[u]) ans[edp[u]] = cnt[u];
    for (int v : e[u]) cnt[v] += cnt[u], dfs(v);
  }
  void mian() {
    for (int i = (2), iE = (tn); i <= iE; i++) e[a[i].nxt].push_back(i);
    dfs(1);
  }
} SAM1, SAM2;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  SAM1.init_SAM(), SAM2.init_SAM();
  cin >> str >> n;
  lent = str.size();
  for (int i = (0), iE = (lent - 1); i <= iE; i++) t[i] = str[i] - 'a';
  for (int i = (0), iE = (lent - 1); i <= iE; i++) SAM1.extend_SAM(t[i]);
  for (int i = (lent - 1), iE = (0); i >= iE; i--) SAM2.extend_SAM(t[i]);
  for (int i = (1), iE = (n); i <= iE; i++) {
    cin >> str;
    SAM1.solve(str);
    reverse(str.begin(), str.end());
    SAM2.solve(str);
  }
  SAM1.mian();
  SAM2.mian();
  long long ans = 0;
  for (int i = (0), iE = (lent - 2); i <= iE; i++)
    ans += 1ll * SAM1.ans[i] * SAM2.ans[lent - i - 2];
  cout << ans;
}

```