#include <bits/stdc++.h>
using namespace std;
string txt[200005], str;
int sz[200005], len[200005], now[200005], child[200005][26], fail[200005],
    par[200005], cnt;
long long vis[200005], st[200005];
void insrt(int n) {
  for (int i = 0; i <= max(cnt, n); i++)
    len[i] = 0, now[i] = 0, fail[i] = 0, par[i] = 0, vis[i] = 0;
  memset(child[0], -1, sizeof child[0]);
  cnt = 0;
  queue<int> q;
  for (int i = 0; i < n; i++) {
    int l = txt[i][0] - 'a';
    if (child[0][l] == -1) {
      ++cnt;
      memset(child[cnt], -1, sizeof child[cnt]);
      child[0][l] = cnt;
    }
    now[i] = child[0][l];
    len[i]++;
    if (len[i] != sz[i])
      q.push(i);
    else
      vis[now[i]]++;
  }
  while (!q.empty()) {
    int i = q.front();
    q.pop();
    int l = txt[i][len[i]] - 'a';
    if (child[now[i]][l] == -1) {
      ++cnt;
      memset(child[cnt], -1, sizeof child[cnt]);
      child[now[i]][l] = cnt;
      par[cnt] = now[i];
    }
    now[i] = child[now[i]][l];
    int x = fail[par[now[i]]];
    while (x && child[x][l] == -1) x = fail[x];
    if (child[x][l] != -1)
      fail[now[i]] = child[x][l];
    else
      fail[now[i]] = 0;
    len[i]++;
    if (len[i] != sz[i])
      q.push(i);
    else
      vis[now[i]]++;
  }
  return;
}
void func() {
  for (int i = 1; i <= cnt; i++) vis[i] += vis[fail[i]];
  return;
}
long long res;
void travers1() {
  int nw = 0;
  for (int i = 0, j = str.size() - 1; str[i]; i++, j--) {
    while (nw && child[nw][str[i] - 'a'] == -1) nw = fail[nw];
    if (child[nw][str[i] - 'a'] != -1) {
      nw = child[nw][str[i] - 'a'];
      st[j] = vis[nw];
    }
  }
  return;
}
void travers2() {
  int nw = 0;
  for (int i = 0; str[i]; i++) {
    while (nw && child[nw][str[i] - 'a'] == -1) nw = fail[nw];
    if (child[nw][str[i] - 'a'] != -1) {
      nw = child[nw][str[i] - 'a'];
      res += vis[nw] * st[i + 1];
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> str >> n;
  reverse(str.begin(), str.end());
  for (int i = 0; i < n; i++)
    cin >> txt[i], sz[i] = txt[i].size(), reverse(txt[i].begin(), txt[i].end());
  insrt(n);
  func();
  travers1();
  reverse(str.begin(), str.end());
  for (int i = 0; i < n; i++)
    sz[i] = txt[i].size(), reverse(txt[i].begin(), txt[i].end());
  insrt(n);
  func();
  travers2();
  printf("%lld\n", res);
  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;
string txt[200005], str;
int sz[200005], len[200005], now[200005], child[200005][26], fail[200005],
    par[200005], cnt;
long long vis[200005], st[200005];
void insrt(int n) {
  for (int i = 0; i <= max(cnt, n); i++)
    len[i] = 0, now[i] = 0, fail[i] = 0, par[i] = 0, vis[i] = 0;
  memset(child[0], -1, sizeof child[0]);
  cnt = 0;
  queue<int> q;
  for (int i = 0; i < n; i++) {
    int l = txt[i][0] - 'a';
    if (child[0][l] == -1) {
      ++cnt;
      memset(child[cnt], -1, sizeof child[cnt]);
      child[0][l] = cnt;
    }
    now[i] = child[0][l];
    len[i]++;
    if (len[i] != sz[i])
      q.push(i);
    else
      vis[now[i]]++;
  }
  while (!q.empty()) {
    int i = q.front();
    q.pop();
    int l = txt[i][len[i]] - 'a';
    if (child[now[i]][l] == -1) {
      ++cnt;
      memset(child[cnt], -1, sizeof child[cnt]);
      child[now[i]][l] = cnt;
      par[cnt] = now[i];
    }
    now[i] = child[now[i]][l];
    int x = fail[par[now[i]]];
    while (x && child[x][l] == -1) x = fail[x];
    if (child[x][l] != -1)
      fail[now[i]] = child[x][l];
    else
      fail[now[i]] = 0;
    len[i]++;
    if (len[i] != sz[i])
      q.push(i);
    else
      vis[now[i]]++;
  }
  return;
}
void func() {
  for (int i = 1; i <= cnt; i++) vis[i] += vis[fail[i]];
  return;
}
long long res;
void travers1() {
  int nw = 0;
  for (int i = 0, j = str.size() - 1; str[i]; i++, j--) {
    while (nw && child[nw][str[i] - 'a'] == -1) nw = fail[nw];
    if (child[nw][str[i] - 'a'] != -1) {
      nw = child[nw][str[i] - 'a'];
      st[j] = vis[nw];
    }
  }
  return;
}
void travers2() {
  int nw = 0;
  for (int i = 0; str[i]; i++) {
    while (nw && child[nw][str[i] - 'a'] == -1) nw = fail[nw];
    if (child[nw][str[i] - 'a'] != -1) {
      nw = child[nw][str[i] - 'a'];
      res += vis[nw] * st[i + 1];
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> str >> n;
  reverse(str.begin(), str.end());
  for (int i = 0; i < n; i++)
    cin >> txt[i], sz[i] = txt[i].size(), reverse(txt[i].begin(), txt[i].end());
  insrt(n);
  func();
  travers1();
  reverse(str.begin(), str.end());
  for (int i = 0; i < n; i++)
    sz[i] = txt[i].size(), reverse(txt[i].begin(), txt[i].end());
  insrt(n);
  func();
  travers2();
  printf("%lld\n", res);
  return 0;
}

```