#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
bool vis[MAXN];
int n, m, qid, id[MAXN], res[MAXN], sz[MAXN], cnt[MAXN];
long long c[2 * MAXN];
string s;
vector<int> g[MAXN];
struct vertex {
  int next[26], go[26];
  int p, link, bad = 0;
  vector<int> leaf;
  char pch;
  vertex(int p = -1, char pch = -1) : p(p), link(-1), pch(pch) {
    memset(next, -1, sizeof(next));
    memset(go, -1, sizeof(go));
  }
};
vector<vertex> t;
void aho_init() {
  t.clear();
  t.push_back(vertex());
}
int add_string(string &s) {
  int v = 0;
  for (char c : s) {
    if (t[v].next[c - 'a'] < 0) {
      t[v].next[c - 'a'] = ((int)(t).size());
      t.push_back(vertex(v, c - 'a'));
    }
    v = t[v].next[c - 'a'];
  }
  if (!t[v].leaf.size()) {
    sz[qid] = ((int)(s).size());
    t[v].leaf.push_back(qid++);
  }
  cnt[t[v].leaf[0]]++;
  return t[v].leaf[0];
}
int go(int v, int c);
int get_link(int v) {
  if (t[v].link < 0) {
    if (!v || !t[v].p)
      t[v].link = 0;
    else
      t[v].link = go(get_link(t[v].p), t[v].pch);
  }
  return t[v].link;
}
int go(int v, int c) {
  if (t[v].go[c] < 0) {
    if (t[v].next[c] >= 0)
      t[v].go[c] = t[v].next[c];
    else
      t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
  }
  return t[v].go[c];
}
void setup(int i) {
  if (!i || vis[i]) return;
  vis[i] = 1;
  setup(get_link(i));
  for (int j : t[get_link(i)].leaf) t[i].leaf.push_back(j);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s >> m;
  aho_init();
  for (int i = 0, ggdem = m; i < ggdem; i++) {
    string tmp;
    cin >> tmp;
    id[i] = add_string(tmp);
  }
  for (int i = 0, ggdem = ((int)(t).size()); i < ggdem; i++) setup(i);
  int pos = 0;
  for (int i = 0, ggdem = ((int)(s).size()); i < ggdem; i++) {
    pos = go(pos, s[i] - 'a');
    for (int j : t[pos].leaf) c[i - sz[j] + 1] += 1ll * cnt[j];
  }
  long long res = 0;
  pos = 0;
  for (int i = 0, ggdem = ((int)(s).size()); i < ggdem; i++) {
    pos = go(pos, s[i] - 'a');
    for (int j : t[pos].leaf) res += 1ll * cnt[j] * c[i + 1];
  }
  cout << res << endl;
}

### Prompt

Create a solution in Cpp for 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;
bool vis[MAXN];
int n, m, qid, id[MAXN], res[MAXN], sz[MAXN], cnt[MAXN];
long long c[2 * MAXN];
string s;
vector<int> g[MAXN];
struct vertex {
  int next[26], go[26];
  int p, link, bad = 0;
  vector<int> leaf;
  char pch;
  vertex(int p = -1, char pch = -1) : p(p), link(-1), pch(pch) {
    memset(next, -1, sizeof(next));
    memset(go, -1, sizeof(go));
  }
};
vector<vertex> t;
void aho_init() {
  t.clear();
  t.push_back(vertex());
}
int add_string(string &s) {
  int v = 0;
  for (char c : s) {
    if (t[v].next[c - 'a'] < 0) {
      t[v].next[c - 'a'] = ((int)(t).size());
      t.push_back(vertex(v, c - 'a'));
    }
    v = t[v].next[c - 'a'];
  }
  if (!t[v].leaf.size()) {
    sz[qid] = ((int)(s).size());
    t[v].leaf.push_back(qid++);
  }
  cnt[t[v].leaf[0]]++;
  return t[v].leaf[0];
}
int go(int v, int c);
int get_link(int v) {
  if (t[v].link < 0) {
    if (!v || !t[v].p)
      t[v].link = 0;
    else
      t[v].link = go(get_link(t[v].p), t[v].pch);
  }
  return t[v].link;
}
int go(int v, int c) {
  if (t[v].go[c] < 0) {
    if (t[v].next[c] >= 0)
      t[v].go[c] = t[v].next[c];
    else
      t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
  }
  return t[v].go[c];
}
void setup(int i) {
  if (!i || vis[i]) return;
  vis[i] = 1;
  setup(get_link(i));
  for (int j : t[get_link(i)].leaf) t[i].leaf.push_back(j);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s >> m;
  aho_init();
  for (int i = 0, ggdem = m; i < ggdem; i++) {
    string tmp;
    cin >> tmp;
    id[i] = add_string(tmp);
  }
  for (int i = 0, ggdem = ((int)(t).size()); i < ggdem; i++) setup(i);
  int pos = 0;
  for (int i = 0, ggdem = ((int)(s).size()); i < ggdem; i++) {
    pos = go(pos, s[i] - 'a');
    for (int j : t[pos].leaf) c[i - sz[j] + 1] += 1ll * cnt[j];
  }
  long long res = 0;
  pos = 0;
  for (int i = 0, ggdem = ((int)(s).size()); i < ggdem; i++) {
    pos = go(pos, s[i] - 'a');
    for (int j : t[pos].leaf) res += 1ll * cnt[j] * c[i + 1];
  }
  cout << res << endl;
}

```