#include <bits/stdc++.h>
using namespace std;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
const int maxn = 1e6 + 5;
const int MAG = 500;
string t;
string s[maxn];
int n, len;
long long cnt[2][maxn];
struct node {
  int count;
  node *ch[26];
  node() {
    count = 0;
    for (int i = 0; i < 26; i++) {
      ch[i] = NULL;
    }
  }
};
void add(string &s, node *cur) {
  for (char c : s) {
    if (cur->ch[c - 'a'] == NULL) {
      cur->ch[c - 'a'] = new node();
    }
    cur = cur->ch[c - 'a'];
  }
  cur->count++;
}
vector<int> prefix_fn(string s) {
  int n = s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) {
      j = pi[j - 1];
    }
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
node *root;
int dfs(int ti) {
  int res = 0;
  node *cur = root;
  assert(cur != NULL);
  for (; ti < len; ti++) {
    cur = cur->ch[t[ti] - 'a'];
    if (cur == NULL) break;
    res += cur->count;
  }
  return res;
}
void dfs0(node *cur, string buf) {
  if (cur == NULL) return;
  if (cur->count) {
    cout << buf << ": " << cur->count << endl;
  }
  for (int i = 0; i < 26; i++) {
    buf += char(i + 'a');
    dfs0(cur->ch[i], buf);
    buf.pop_back();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  len = t.length();
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  for (int k = 0; k < 2; k++) {
    root = new node();
    for (int i = 0; i < n; i++) {
      if (int(s[i].length()) > MAG) {
        auto pi = prefix_fn(s[i] + "$" + t);
        for (int j = 0; j < len; j++) {
          int e = (int)s[i].length() + 1 + j + (int)s[i].length() - 1;
          if (e < int(pi.size())) {
            if (pi[e] >= (int)s[i].length()) {
              cnt[k][j]++;
            }
          }
        }
      } else {
        add(s[i], root);
      }
    }
    for (int i = 0; i < len; i++) {
      cnt[k][i] += dfs(i);
    }
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
      reverse(s[i].begin(), s[i].end());
    }
  }
  long long ans = 0;
  for (int i = 0; i < len; i++) {
    long long cur = cnt[0][i] * cnt[1][len - i];
    ans += cur;
  }
  cout << ans << endl;
  return 0;
}

### 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;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
const int maxn = 1e6 + 5;
const int MAG = 500;
string t;
string s[maxn];
int n, len;
long long cnt[2][maxn];
struct node {
  int count;
  node *ch[26];
  node() {
    count = 0;
    for (int i = 0; i < 26; i++) {
      ch[i] = NULL;
    }
  }
};
void add(string &s, node *cur) {
  for (char c : s) {
    if (cur->ch[c - 'a'] == NULL) {
      cur->ch[c - 'a'] = new node();
    }
    cur = cur->ch[c - 'a'];
  }
  cur->count++;
}
vector<int> prefix_fn(string s) {
  int n = s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) {
      j = pi[j - 1];
    }
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
node *root;
int dfs(int ti) {
  int res = 0;
  node *cur = root;
  assert(cur != NULL);
  for (; ti < len; ti++) {
    cur = cur->ch[t[ti] - 'a'];
    if (cur == NULL) break;
    res += cur->count;
  }
  return res;
}
void dfs0(node *cur, string buf) {
  if (cur == NULL) return;
  if (cur->count) {
    cout << buf << ": " << cur->count << endl;
  }
  for (int i = 0; i < 26; i++) {
    buf += char(i + 'a');
    dfs0(cur->ch[i], buf);
    buf.pop_back();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  len = t.length();
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  for (int k = 0; k < 2; k++) {
    root = new node();
    for (int i = 0; i < n; i++) {
      if (int(s[i].length()) > MAG) {
        auto pi = prefix_fn(s[i] + "$" + t);
        for (int j = 0; j < len; j++) {
          int e = (int)s[i].length() + 1 + j + (int)s[i].length() - 1;
          if (e < int(pi.size())) {
            if (pi[e] >= (int)s[i].length()) {
              cnt[k][j]++;
            }
          }
        }
      } else {
        add(s[i], root);
      }
    }
    for (int i = 0; i < len; i++) {
      cnt[k][i] += dfs(i);
    }
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
      reverse(s[i].begin(), s[i].end());
    }
  }
  long long ans = 0;
  for (int i = 0; i < len; i++) {
    long long cur = cnt[0][i] * cnt[1][len - i];
    ans += cur;
  }
  cout << ans << endl;
  return 0;
}

```