#include <bits/stdc++.h>
using namespace std;
struct vertex {
  vector<int> next, go;
  int p, link;
  char pch;
  vector<int> leaf;
  vertex(int p = -1, char pch = -1) : p(p), pch(pch), link(-1) {
    next = vector<int>(26, -1);
    go = vector<int>(26, -1);
  }
};
vector<vertex> t;
void aho_init() {
  t.clear();
  t.push_back(vertex());
}
void add_string(string s, int id) {
  int v = 0;
  for (char c : s) {
    if (t[v].next[c - 'a'] < 0) {
      t[v].next[c - 'a'] = t.size();
      t.push_back(vertex(v, c));
    }
    v = t[v].next[c - 'a'];
  }
  t[v].leaf.push_back(id);
}
int go(int v, char 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, char c) {
  if (t[v].go[c - 'a'] < 0)
    if (t[v].next[c - 'a'] >= 0)
      t[v].go[c - 'a'] = t[v].next[c - 'a'];
    else
      t[v].go[c - 'a'] = v == 0 ? 0 : go(get_link(v), c);
  return t[v].go[c - 'a'];
}
int dp[200010];
int firmatch(int v) {
  if (!v) return 0;
  int &r = dp[v];
  if (r >= 0) return r;
  return r = int(t[v].leaf.size()) ? v : firmatch(get_link(v));
}
long long cnt[200010];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(dp, -1, sizeof(dp));
  aho_init();
  map<string, int> mp;
  int n, id = 0;
  string s;
  cin >> s >> n;
  vector<int> q, len;
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
    string t;
    cin >> t;
    if (!mp.count(t))
      add_string(t, id), len.push_back(int(t.size())), mp[t] = id++;
    cnt[mp[t]]++;
    q.push_back(mp[t]);
  }
  vector<long long> ans(id);
  vector<long long> aps(int(s.size()) + 1);
  int v = 0;
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i) {
    v = go(v, s[i]);
    int now = firmatch(v);
    while (int(t[now].leaf.size())) {
      int dd = t[now].leaf[0];
      aps[i - len[dd] + 1] += cnt[dd];
      now = firmatch(get_link(now));
    }
  }
  v = 0;
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i) {
    v = go(v, s[i]);
    int now = firmatch(v);
    while (int(t[now].leaf.size())) {
      int dd = t[now].leaf[0];
      ans[dd] += aps[i + 1];
      now = firmatch(get_link(now));
    }
  }
  long long tot = 0;
  for (auto x : q) tot += ans[x];
  cout << tot << "\n";
}

### 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;
struct vertex {
  vector<int> next, go;
  int p, link;
  char pch;
  vector<int> leaf;
  vertex(int p = -1, char pch = -1) : p(p), pch(pch), link(-1) {
    next = vector<int>(26, -1);
    go = vector<int>(26, -1);
  }
};
vector<vertex> t;
void aho_init() {
  t.clear();
  t.push_back(vertex());
}
void add_string(string s, int id) {
  int v = 0;
  for (char c : s) {
    if (t[v].next[c - 'a'] < 0) {
      t[v].next[c - 'a'] = t.size();
      t.push_back(vertex(v, c));
    }
    v = t[v].next[c - 'a'];
  }
  t[v].leaf.push_back(id);
}
int go(int v, char 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, char c) {
  if (t[v].go[c - 'a'] < 0)
    if (t[v].next[c - 'a'] >= 0)
      t[v].go[c - 'a'] = t[v].next[c - 'a'];
    else
      t[v].go[c - 'a'] = v == 0 ? 0 : go(get_link(v), c);
  return t[v].go[c - 'a'];
}
int dp[200010];
int firmatch(int v) {
  if (!v) return 0;
  int &r = dp[v];
  if (r >= 0) return r;
  return r = int(t[v].leaf.size()) ? v : firmatch(get_link(v));
}
long long cnt[200010];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(dp, -1, sizeof(dp));
  aho_init();
  map<string, int> mp;
  int n, id = 0;
  string s;
  cin >> s >> n;
  vector<int> q, len;
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
    string t;
    cin >> t;
    if (!mp.count(t))
      add_string(t, id), len.push_back(int(t.size())), mp[t] = id++;
    cnt[mp[t]]++;
    q.push_back(mp[t]);
  }
  vector<long long> ans(id);
  vector<long long> aps(int(s.size()) + 1);
  int v = 0;
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i) {
    v = go(v, s[i]);
    int now = firmatch(v);
    while (int(t[now].leaf.size())) {
      int dd = t[now].leaf[0];
      aps[i - len[dd] + 1] += cnt[dd];
      now = firmatch(get_link(now));
    }
  }
  v = 0;
  for (int i = 0, ThxDem = int(s.size()); i < ThxDem; ++i) {
    v = go(v, s[i]);
    int now = firmatch(v);
    while (int(t[now].leaf.size())) {
      int dd = t[now].leaf[0];
      ans[dd] += aps[i + 1];
      now = firmatch(get_link(now));
    }
  }
  long long tot = 0;
  for (auto x : q) tot += ans[x];
  cout << tot << "\n";
}

```