#include <bits/stdc++.h>
using namespace std;
struct AC {
  static const int K = 26;
  struct node {
    int nxt[K], link, leaf = 0, par;
    char pch;
    node(int par = -1, char pch = '$') : par(par), pch(pch) {
      fill(begin(nxt), end(nxt), -1);
      leaf = false;
      link = -1;
    }
  };
  vector<node> t;
  vector<vector<int> > ad;
  vector<int> st, en, mp, dp;
  int dt = 0;
  AC() {
    mp = vector<int>(1 << 8, 0);
    for (char ch = 'a'; ch <= 'z'; ++ch) mp[ch] = ch - 'a';
    t.resize(1);
  }
  int add(string str) {
    int ptr = 0;
    for (auto ch : str) {
      if (t[ptr].nxt[mp[ch]] < 0) {
        t[ptr].nxt[mp[ch]] = t.size();
        t.push_back(node(ptr, ch));
      }
      ptr = t[ptr].nxt[mp[ch]];
    }
    t[ptr].leaf++;
    return ptr;
  }
  int get_link(int v) {
    if (t[v].link == -1) {
      t[v].link = (!v || !t[v].par) ? 0 : go(get_link(t[v].par), t[v].pch);
    }
    return t[v].link;
  }
  int go(int v, char ch) {
    if (t[v].nxt[mp[ch]] < 0) {
      t[v].nxt[mp[ch]] = !v ? 0 : go(get_link(v), ch);
    }
    return t[v].nxt[mp[ch]];
  }
  void dfs(int v) {
    dp[v] = t[v].leaf + dp[get_link(v)];
    for (int u : ad[v]) dfs(u);
  }
  void calc() {
    int k = t.size();
    dp.resize(k);
    ad.resize(k);
    for (int i = 1; i < k; i++) ad[get_link(i)].push_back(i);
    dfs(0);
  }
} a, b;
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string str;
  cin >> str;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    a.add(s);
    reverse(s.begin(), s.end());
    b.add(s);
  }
  a.calc();
  b.calc();
  int m = str.size(), v = 0;
  vector<int> p(m + 2, 0), q(m + 2, 0);
  for (int i = 0; i < m; i++) {
    v = a.go(v, str[i]);
    p[i] = a.dp[v];
  }
  v = 0;
  for (int i = m - 1; i >= 0; i--) {
    v = b.go(v, str[i]);
    q[i] = b.dp[v];
  }
  long long ans = 0;
  for (int i = 0; i < m - 1; i++) ans += 1LL * p[i] * q[i + 1];
  cout << ans << endl;
}

### 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;
struct AC {
  static const int K = 26;
  struct node {
    int nxt[K], link, leaf = 0, par;
    char pch;
    node(int par = -1, char pch = '$') : par(par), pch(pch) {
      fill(begin(nxt), end(nxt), -1);
      leaf = false;
      link = -1;
    }
  };
  vector<node> t;
  vector<vector<int> > ad;
  vector<int> st, en, mp, dp;
  int dt = 0;
  AC() {
    mp = vector<int>(1 << 8, 0);
    for (char ch = 'a'; ch <= 'z'; ++ch) mp[ch] = ch - 'a';
    t.resize(1);
  }
  int add(string str) {
    int ptr = 0;
    for (auto ch : str) {
      if (t[ptr].nxt[mp[ch]] < 0) {
        t[ptr].nxt[mp[ch]] = t.size();
        t.push_back(node(ptr, ch));
      }
      ptr = t[ptr].nxt[mp[ch]];
    }
    t[ptr].leaf++;
    return ptr;
  }
  int get_link(int v) {
    if (t[v].link == -1) {
      t[v].link = (!v || !t[v].par) ? 0 : go(get_link(t[v].par), t[v].pch);
    }
    return t[v].link;
  }
  int go(int v, char ch) {
    if (t[v].nxt[mp[ch]] < 0) {
      t[v].nxt[mp[ch]] = !v ? 0 : go(get_link(v), ch);
    }
    return t[v].nxt[mp[ch]];
  }
  void dfs(int v) {
    dp[v] = t[v].leaf + dp[get_link(v)];
    for (int u : ad[v]) dfs(u);
  }
  void calc() {
    int k = t.size();
    dp.resize(k);
    ad.resize(k);
    for (int i = 1; i < k; i++) ad[get_link(i)].push_back(i);
    dfs(0);
  }
} a, b;
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string str;
  cin >> str;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    a.add(s);
    reverse(s.begin(), s.end());
    b.add(s);
  }
  a.calc();
  b.calc();
  int m = str.size(), v = 0;
  vector<int> p(m + 2, 0), q(m + 2, 0);
  for (int i = 0; i < m; i++) {
    v = a.go(v, str[i]);
    p[i] = a.dp[v];
  }
  v = 0;
  for (int i = m - 1; i >= 0; i--) {
    v = b.go(v, str[i]);
    q[i] = b.dp[v];
  }
  long long ans = 0;
  for (int i = 0; i < m - 1; i++) ans += 1LL * p[i] * q[i + 1];
  cout << ans << endl;
}

```