#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 5;
int n, cnt[2][N];
long long ans;
string t, s[N];
struct Aho {
  vector<vector<int> > gr;
  vector<int> val;
  int nNode = 0;
  struct Node {
    int child[26], nxt[26], link, cnt;
    Node() {
      memset(child, 0, sizeof child);
      memset(nxt, 0, sizeof nxt);
      cnt = link = 0;
    }
  } node[N];
  void reset() {
    val.clear();
    gr.clear();
    for (int i = 0; i <= nNode; ++i) node[i] = Node();
    nNode = 0;
  }
  void addString(string str) {
    int curNode = 0;
    for (int i = 0; i < (int)str.size(); ++i) {
      int ch = str[i] - 'a';
      if (!node[curNode].child[ch]) node[curNode].child[ch] = ++nNode;
      curNode = node[curNode].child[ch];
    }
    ++node[curNode].cnt;
  }
  void bfs() {
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int ch = 0; ch < 26; ++ch) {
        int v = node[u].child[ch];
        node[u].nxt[ch] = node[node[u].link].nxt[ch];
        if (v) {
          node[v].link = node[u].nxt[ch];
          node[u].nxt[ch] = v;
          q.push(v);
        }
      }
    }
  }
  void dfs(int u) {
    for (int v : gr[u]) {
      val[v] = node[v].cnt + val[u];
      dfs(v);
    }
  }
  void prep() {
    gr.assign(nNode + 5, vector<int>());
    for (int i = 1; i <= nNode; ++i) gr[node[i].link].push_back(i);
    val.assign(nNode + 5, 0);
    dfs(0);
  }
} aho;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    aho.addString(s[i]);
  }
  aho.bfs();
  aho.prep();
  for (int i = 0, cur_node = 0; i < (int)t.size(); ++i) {
    cur_node = aho.node[cur_node].nxt[t[i] - 'a'];
    cnt[0][i] = aho.val[cur_node];
  }
  aho.reset();
  reverse(t.begin(), t.end());
  for (int i = 1; i <= n; ++i) {
    reverse(s[i].begin(), s[i].end());
    aho.addString(s[i]);
  }
  aho.bfs();
  aho.prep();
  for (int i = 0, cur_node = 0; i + 1 < (int)t.size(); ++i) {
    cur_node = aho.node[cur_node].nxt[t[i] - 'a'];
    cnt[1][i] = aho.val[cur_node];
    ans += 1LL * cnt[0][(int)t.size() - 1 - (i + 1)] * cnt[1][i];
  }
  cout << ans;
  return 0;
}

### Prompt

Develop a solution in Cpp 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 = (int)2e5 + 5;
int n, cnt[2][N];
long long ans;
string t, s[N];
struct Aho {
  vector<vector<int> > gr;
  vector<int> val;
  int nNode = 0;
  struct Node {
    int child[26], nxt[26], link, cnt;
    Node() {
      memset(child, 0, sizeof child);
      memset(nxt, 0, sizeof nxt);
      cnt = link = 0;
    }
  } node[N];
  void reset() {
    val.clear();
    gr.clear();
    for (int i = 0; i <= nNode; ++i) node[i] = Node();
    nNode = 0;
  }
  void addString(string str) {
    int curNode = 0;
    for (int i = 0; i < (int)str.size(); ++i) {
      int ch = str[i] - 'a';
      if (!node[curNode].child[ch]) node[curNode].child[ch] = ++nNode;
      curNode = node[curNode].child[ch];
    }
    ++node[curNode].cnt;
  }
  void bfs() {
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int ch = 0; ch < 26; ++ch) {
        int v = node[u].child[ch];
        node[u].nxt[ch] = node[node[u].link].nxt[ch];
        if (v) {
          node[v].link = node[u].nxt[ch];
          node[u].nxt[ch] = v;
          q.push(v);
        }
      }
    }
  }
  void dfs(int u) {
    for (int v : gr[u]) {
      val[v] = node[v].cnt + val[u];
      dfs(v);
    }
  }
  void prep() {
    gr.assign(nNode + 5, vector<int>());
    for (int i = 1; i <= nNode; ++i) gr[node[i].link].push_back(i);
    val.assign(nNode + 5, 0);
    dfs(0);
  }
} aho;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    aho.addString(s[i]);
  }
  aho.bfs();
  aho.prep();
  for (int i = 0, cur_node = 0; i < (int)t.size(); ++i) {
    cur_node = aho.node[cur_node].nxt[t[i] - 'a'];
    cnt[0][i] = aho.val[cur_node];
  }
  aho.reset();
  reverse(t.begin(), t.end());
  for (int i = 1; i <= n; ++i) {
    reverse(s[i].begin(), s[i].end());
    aho.addString(s[i]);
  }
  aho.bfs();
  aho.prep();
  for (int i = 0, cur_node = 0; i + 1 < (int)t.size(); ++i) {
    cur_node = aho.node[cur_node].nxt[t[i] - 'a'];
    cnt[1][i] = aho.val[cur_node];
    ans += 1LL * cnt[0][(int)t.size() - 1 - (i + 1)] * cnt[1][i];
  }
  cout << ans;
  return 0;
}

```