#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 5;
int n, m, cntNode(2), root(1), root2(2), f[MAXN], g[MAXN];
string T, s;
struct Trie {
  int son[26], fail, cntEnd;
  Trie() {
    for (int i = 0; i < 26; i++) son[i] = 0;
    fail = cntEnd = 0;
  }
} tr[MAXN * 2];
void insert(int root, string& s) {
  int cur = root;
  for (int i = 0; i < s.size(); i++) {
    if (!tr[cur].son[s[i] - 'a']) tr[cur].son[s[i] - 'a'] = ++cntNode;
    cur = tr[cur].son[s[i] - 'a'];
  }
  tr[cur].cntEnd++;
}
void getFail(int root) {
  queue<int> Q;
  Q.push(root);
  tr[root].fail = root;
  while (!Q.empty()) {
    int now = Q.front();
    Q.pop();
    tr[now].cntEnd += tr[tr[now].fail].cntEnd;
    for (int i = 0; i < 26; i++) {
      if (tr[now].son[i]) {
        tr[tr[now].son[i]].fail = now != root ? tr[tr[now].fail].son[i] : root;
        Q.push(tr[now].son[i]);
      } else
        tr[now].son[i] =
            tr[tr[now].fail].son[i] ? tr[tr[now].fail].son[i] : root;
    }
  }
}
void match(string& s) {
  int cur = root;
  for (int i = 0; i < s.size(); i++) {
    int to = tr[cur].son[s[i] - 'a'];
    f[i] = tr[to].cntEnd;
    cur = to;
  }
  reverse(s.begin(), s.end());
  cur = root2;
  for (int i = 0; i < s.size(); i++) {
    int to = tr[cur].son[s[i] - 'a'];
    g[s.size() - i - 1] = tr[to].cntEnd;
    cur = to;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin >> T >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s, insert(root, s);
    reverse(s.begin(), s.end());
    insert(root2, s);
  }
  getFail(root), getFail(root2);
  match(T);
  long long ans = 0;
  for (int i = 0; i < T.size() - 1; i++) ans += 1ll * f[i] * g[i + 1];
  cout << ans;
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
const int MAXN = 2E5 + 5;
int n, m, cntNode(2), root(1), root2(2), f[MAXN], g[MAXN];
string T, s;
struct Trie {
  int son[26], fail, cntEnd;
  Trie() {
    for (int i = 0; i < 26; i++) son[i] = 0;
    fail = cntEnd = 0;
  }
} tr[MAXN * 2];
void insert(int root, string& s) {
  int cur = root;
  for (int i = 0; i < s.size(); i++) {
    if (!tr[cur].son[s[i] - 'a']) tr[cur].son[s[i] - 'a'] = ++cntNode;
    cur = tr[cur].son[s[i] - 'a'];
  }
  tr[cur].cntEnd++;
}
void getFail(int root) {
  queue<int> Q;
  Q.push(root);
  tr[root].fail = root;
  while (!Q.empty()) {
    int now = Q.front();
    Q.pop();
    tr[now].cntEnd += tr[tr[now].fail].cntEnd;
    for (int i = 0; i < 26; i++) {
      if (tr[now].son[i]) {
        tr[tr[now].son[i]].fail = now != root ? tr[tr[now].fail].son[i] : root;
        Q.push(tr[now].son[i]);
      } else
        tr[now].son[i] =
            tr[tr[now].fail].son[i] ? tr[tr[now].fail].son[i] : root;
    }
  }
}
void match(string& s) {
  int cur = root;
  for (int i = 0; i < s.size(); i++) {
    int to = tr[cur].son[s[i] - 'a'];
    f[i] = tr[to].cntEnd;
    cur = to;
  }
  reverse(s.begin(), s.end());
  cur = root2;
  for (int i = 0; i < s.size(); i++) {
    int to = tr[cur].son[s[i] - 'a'];
    g[s.size() - i - 1] = tr[to].cntEnd;
    cur = to;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin >> T >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s, insert(root, s);
    reverse(s.begin(), s.end());
    insert(root2, s);
  }
  getFail(root), getFail(root2);
  match(T);
  long long ans = 0;
  for (int i = 0; i < T.size() - 1; i++) ans += 1ll * f[i] * g[i + 1];
  cout << ans;
  return 0;
}

```