#include <bits/stdc++.h>
using namespace std;
const int N = 400000 + 10;
const int M = 26;
namespace Trie {
int trie[N][M], cnt[N], size;
void init() {
  size = 0;
  memset(trie[0], 0, sizeof(trie[0]));
  cnt[0] = 0;
}
void insert(char str[]) {
  int u = 0, v;
  for (int i = 0; str[i]; i++) {
    v = str[i] - 'a';
    if (!trie[u][v]) {
      trie[u][v] = ++size;
      cnt[size] = 0;
      memset(trie[size], 0, sizeof(trie[size]));
    }
    u = trie[u][v];
  }
  cnt[u]++;
}
}  // namespace Trie
namespace SAM {
struct state {
  int len, link, siz;
  int next[M];
} st[N];
int sz, last;
void init() {
  sz = 1, last = 0;
  st[0].len = 0;
  st[0].link = -1;
}
void add(int c) {
  int r = sz++;
  st[r].len = st[last].len + 1;
  st[r].siz = 1;
  int p = last;
  while (p != -1 && !st[p].next[c]) st[p].next[c] = r, p = st[p].link;
  if (p == -1)
    st[r].link = 0;
  else {
    int q = st[p].next[c];
    if (st[q].len == st[p].len + 1)
      st[r].link = q;
    else {
      int qq = sz++;
      st[qq].link = st[q].link;
      memcpy(st[qq].next, st[q].next, sizeof(st[q].next));
      st[qq].len = st[p].len + 1;
      st[qq].siz = 0;
      while (p != -1 && st[p].next[c] == q) st[p].next[c] = qq, p = st[p].link;
      st[q].link = st[r].link = qq;
    }
  }
  last = r;
}
int tp[N], tmp[N];
void get_topo() {
  memset(tmp, 0, sizeof(tmp));
  for (int i = 0; i < sz; i++) tmp[st[i].len]++;
  for (int i = 1; i < sz; i++) tmp[i] += tmp[i - 1];
  for (int i = 0; i < sz; i++) tp[--tmp[st[i].len]] = i;
}
void calc_siz() {
  get_topo();
  for (int i = sz - 1; i > 0; i--) st[st[tp[i]].link].siz += st[tp[i]].siz;
  st[0].siz = 0;
}
}  // namespace SAM
long long dfs(int tu, int su) {
  long long ans = 1ll * Trie::cnt[tu] * SAM::st[su].siz;
  for (int i = 0; i < M; i++) {
    int tv = Trie::trie[tu][i];
    int sv = SAM::st[su].next[i];
    if (tv == 0 || sv == 0) continue;
    ans += dfs(tv, sv);
  }
  return ans;
}
int id[N];
void ddfs(int i) {
  if (id[i] == -1) return;
  for (int j = 0; j < M; j++) {
    int v = Trie::trie[i][j];
    if (v) {
      id[v] = SAM::st[id[i]].next[j];
      if (id[v] == 0) id[v]--;
      ddfs(v);
    }
  }
}
char s[N];
int main() {
  SAM::init(), Trie::init();
  scanf("%s", s);
  for (int i = 0; s[i]; i++) SAM::add(s[i] - 'a');
  SAM::calc_siz();
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", s);
    Trie::insert(s);
  }
  ddfs(0);
  long long ans = 0;
  for (int i = 0; i <= Trie::size; i++) {
    if (id[i] <= 0) continue;
    if (Trie::cnt[i]) ans += 1ll * Trie::cnt[i] * dfs(0, id[i]);
  }
  printf("%lld\n", ans);
}

### 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 = 400000 + 10;
const int M = 26;
namespace Trie {
int trie[N][M], cnt[N], size;
void init() {
  size = 0;
  memset(trie[0], 0, sizeof(trie[0]));
  cnt[0] = 0;
}
void insert(char str[]) {
  int u = 0, v;
  for (int i = 0; str[i]; i++) {
    v = str[i] - 'a';
    if (!trie[u][v]) {
      trie[u][v] = ++size;
      cnt[size] = 0;
      memset(trie[size], 0, sizeof(trie[size]));
    }
    u = trie[u][v];
  }
  cnt[u]++;
}
}  // namespace Trie
namespace SAM {
struct state {
  int len, link, siz;
  int next[M];
} st[N];
int sz, last;
void init() {
  sz = 1, last = 0;
  st[0].len = 0;
  st[0].link = -1;
}
void add(int c) {
  int r = sz++;
  st[r].len = st[last].len + 1;
  st[r].siz = 1;
  int p = last;
  while (p != -1 && !st[p].next[c]) st[p].next[c] = r, p = st[p].link;
  if (p == -1)
    st[r].link = 0;
  else {
    int q = st[p].next[c];
    if (st[q].len == st[p].len + 1)
      st[r].link = q;
    else {
      int qq = sz++;
      st[qq].link = st[q].link;
      memcpy(st[qq].next, st[q].next, sizeof(st[q].next));
      st[qq].len = st[p].len + 1;
      st[qq].siz = 0;
      while (p != -1 && st[p].next[c] == q) st[p].next[c] = qq, p = st[p].link;
      st[q].link = st[r].link = qq;
    }
  }
  last = r;
}
int tp[N], tmp[N];
void get_topo() {
  memset(tmp, 0, sizeof(tmp));
  for (int i = 0; i < sz; i++) tmp[st[i].len]++;
  for (int i = 1; i < sz; i++) tmp[i] += tmp[i - 1];
  for (int i = 0; i < sz; i++) tp[--tmp[st[i].len]] = i;
}
void calc_siz() {
  get_topo();
  for (int i = sz - 1; i > 0; i--) st[st[tp[i]].link].siz += st[tp[i]].siz;
  st[0].siz = 0;
}
}  // namespace SAM
long long dfs(int tu, int su) {
  long long ans = 1ll * Trie::cnt[tu] * SAM::st[su].siz;
  for (int i = 0; i < M; i++) {
    int tv = Trie::trie[tu][i];
    int sv = SAM::st[su].next[i];
    if (tv == 0 || sv == 0) continue;
    ans += dfs(tv, sv);
  }
  return ans;
}
int id[N];
void ddfs(int i) {
  if (id[i] == -1) return;
  for (int j = 0; j < M; j++) {
    int v = Trie::trie[i][j];
    if (v) {
      id[v] = SAM::st[id[i]].next[j];
      if (id[v] == 0) id[v]--;
      ddfs(v);
    }
  }
}
char s[N];
int main() {
  SAM::init(), Trie::init();
  scanf("%s", s);
  for (int i = 0; s[i]; i++) SAM::add(s[i] - 'a');
  SAM::calc_siz();
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", s);
    Trie::insert(s);
  }
  ddfs(0);
  long long ans = 0;
  for (int i = 0; i <= Trie::size; i++) {
    if (id[i] <= 0) continue;
    if (Trie::cnt[i]) ans += 1ll * Trie::cnt[i] * dfs(0, id[i]);
  }
  printf("%lld\n", ans);
}

```