#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast", "unroll-loops", "omit-frame-pointer", \
                     "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
using namespace std;
template <typename T, typename F>
struct AHO_CORASICK {
  vector<pair<long long, long long>> lim;
  vector<vector<long long>> glink;
  vector<vector<long long>> words;
  vector<unordered_map<F, pair<long long, bool>>> tgo;
  vector<long long> pt_string;
  vector<long long> dict_link;
  vector<long long> vtime;
  vector<long long> link;
  vector<long long> abi;
  vector<long long> ch;
  vector<long long> p;
  long long cant_string = 0;
  long long sz = 0;
  bool ok_match = false;
  bool ok_link_tree = false;
  void init() {
    lim.clear();
    glink.clear();
    words.clear();
    tgo.clear();
    pt_string.clear();
    dict_link.clear();
    vtime.clear();
    link.clear();
    abi.clear();
    ch.clear();
    p.clear();
    cant_string = 0;
    sz = 0;
    ok_match = false;
    ok_link_tree = false;
    new_node(-1, -1);
  }
  void build(vector<T> &vect) {
    init();
    for (long long i = 0; i < vect.size(); i++) {
      add_string(vect[i]);
    }
  }
  long long size() { return sz; }
  void new_node(long long tp, long long tch) {
    sz++;
    tgo.emplace_back();
    dict_link.push_back(-1);
    words.emplace_back();
    link.push_back(-1);
    ch.push_back(tch);
    p.push_back(tp);
  }
  AHO_CORASICK() { init(); }
  void add_string(T cad) {
    long long pt = 0;
    for (long long i = 0; i < cad.size(); i++) {
      F tch = cad[i];
      auto it = &tgo[pt][tch];
      if ((*it).second == false) {
        (*it).second = true;
        (*it).first = sz;
        new_node(pt, tch);
      }
      pt = (*it).first;
    }
    words[pt].push_back(pt_string.size());
    pt_string.push_back(pt);
  }
  void build_link_tree() {
    ok_link_tree = true;
    glink.resize(sz);
    for (long long i = 1; i < sz; i++) {
      glink[get_link(i)].push_back(i);
    }
  }
  void build_match() {
    ok_match = true;
    if (ok_link_tree == false) build_link_tree();
    vtime.resize(sz);
    lim.resize(sz);
    abi.resize(sz + 1);
    long long ct = 0;
    function<void(long long)> DFS = [&](long long nodo) {
      vtime[nodo] = ++ct;
      for (auto v : glink[nodo]) {
        DFS(v);
      }
      lim[nodo] = {vtime[nodo], ct};
    };
    DFS(0);
  }
  void abi_update(long long x, long long v) {
    while (x < abi.size()) {
      abi[x] += v;
      x += x & -x;
    }
  }
  long long abi_query(long long x) {
    long long res = 0;
    while (x) {
      res += abi[x];
      x -= x & -x;
    }
    return res;
  }
  long long abi_range(long long a, long long b) {
    return abi_query(b) - abi_query(a - 1);
  }
  vector<long long> match(vector<T> vcad) {
    if (ok_match == false) build_match();
    vector<long long> ups;
    for (auto cad : vcad) {
      long long pt = 0;
      for (long long i = 0; i < cad.size(); i++) {
        pt = go(pt, cad[i]);
        abi_update(vtime[pt], 1);
        ups.push_back(vtime[pt]);
      }
    }
    vector<long long> res(pt_string.size());
    for (long long i = 0; i < pt_string.size(); i++) {
      res[i] = abi_range(lim[pt_string[i]].first, lim[pt_string[i]].second);
    }
    for (auto x : ups) {
      abi_update(x, -1);
    }
    return res;
  }
  vector<long long> match_offline(vector<T> vcad) {
    if (ok_link_tree == false) build_link_tree();
    vector<long long> dp(sz);
    for (auto cad : vcad) {
      long long pt = 0;
      for (long long i = 0; i < cad.size(); i++) {
        pt = go(pt, cad[i]);
        dp[pt]++;
      }
    }
    function<void(long long)> DFS = [&](long long nodo) {
      for (auto v : glink[nodo]) {
        DFS(v);
        dp[nodo] += dp[v];
      }
    };
    DFS(0);
    vector<long long> res(pt_string.size());
    for (long long i = 0; i < pt_string.size(); i++) {
      res[i] = dp[pt_string[i]];
    }
    return res;
  }
  long long get_dictionary_link(long long nodo) {
    if (dict_link[nodo] == -1) {
      if (nodo == 0 || p[nodo] == 0)
        dict_link[nodo] = 0;
      else {
        long long v = get_link(nodo);
        if (words[v].size())
          dict_link[nodo] = v;
        else
          dict_link[nodo] = get_dictionary_link(v);
      }
    }
    return dict_link[nodo];
  }
  long long get_link(long long nodo) {
    if (link[nodo] == -1) {
      if (nodo == 0 || p[nodo] == 0)
        link[nodo] = 0;
      else
        link[nodo] = go(get_link(p[nodo]), ch[nodo]);
    }
    return link[nodo];
  }
  long long go(long long nodo, F tch) {
    auto it = &tgo[nodo][tch];
    if ((*it).second == false) {
      (*it).second = true;
      (*it).first = (nodo == 0) ? 0 : go(get_link(nodo), tch);
    }
    return (*it).first;
  }
};
const long long MAXN = 2e5 + 100;
long long arr1[MAXN];
long long arr2[MAXN];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  AHO_CORASICK<string, char> AC1;
  AHO_CORASICK<string, char> AC2;
  string T;
  cin >> T;
  long long N;
  cin >> N;
  for (long long i = 0; i < N; i++) {
    string cad;
    cin >> cad;
    AC1.add_string(cad);
    reverse(cad.begin(), cad.end());
    AC2.add_string(cad);
  }
  AC1.build_link_tree();
  AC2.build_link_tree();
  vector<long long> cant1(AC1.size());
  vector<long long> cant2(AC2.size());
  for (auto x : AC1.pt_string) {
    cant1[x]++;
  }
  for (auto x : AC2.pt_string) {
    cant2[x]++;
  }
  function<void(long long)> DFS1 = [&](long long nodo) {
    for (auto v : AC1.glink[nodo]) {
      cant1[v] += cant1[nodo];
      DFS1(v);
    }
  };
  DFS1(0);
  function<void(long long)> DFS2 = [&](long long nodo) {
    for (auto v : AC2.glink[nodo]) {
      cant2[v] += cant2[nodo];
      DFS2(v);
    }
  };
  DFS2(0);
  long long pt = 0;
  for (long long i = 0; i < T.size(); i++) {
    pt = AC1.go(pt, T[i]);
    arr1[i] = cant1[pt];
  }
  pt = 0;
  for (long long i = T.size() - 1; i >= 0; i--) {
    pt = AC2.go(pt, T[i]);
    arr2[i] = cant2[pt];
  }
  long long res = 0;
  for (long long i = 0; i < T.size() - 1; i++) {
    res += arr1[i] * arr2[i + 1];
  }
  cout << res << '\n';
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
#pragma GCC optimize("O3", "Ofast", "unroll-loops", "omit-frame-pointer", \
                     "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
using namespace std;
template <typename T, typename F>
struct AHO_CORASICK {
  vector<pair<long long, long long>> lim;
  vector<vector<long long>> glink;
  vector<vector<long long>> words;
  vector<unordered_map<F, pair<long long, bool>>> tgo;
  vector<long long> pt_string;
  vector<long long> dict_link;
  vector<long long> vtime;
  vector<long long> link;
  vector<long long> abi;
  vector<long long> ch;
  vector<long long> p;
  long long cant_string = 0;
  long long sz = 0;
  bool ok_match = false;
  bool ok_link_tree = false;
  void init() {
    lim.clear();
    glink.clear();
    words.clear();
    tgo.clear();
    pt_string.clear();
    dict_link.clear();
    vtime.clear();
    link.clear();
    abi.clear();
    ch.clear();
    p.clear();
    cant_string = 0;
    sz = 0;
    ok_match = false;
    ok_link_tree = false;
    new_node(-1, -1);
  }
  void build(vector<T> &vect) {
    init();
    for (long long i = 0; i < vect.size(); i++) {
      add_string(vect[i]);
    }
  }
  long long size() { return sz; }
  void new_node(long long tp, long long tch) {
    sz++;
    tgo.emplace_back();
    dict_link.push_back(-1);
    words.emplace_back();
    link.push_back(-1);
    ch.push_back(tch);
    p.push_back(tp);
  }
  AHO_CORASICK() { init(); }
  void add_string(T cad) {
    long long pt = 0;
    for (long long i = 0; i < cad.size(); i++) {
      F tch = cad[i];
      auto it = &tgo[pt][tch];
      if ((*it).second == false) {
        (*it).second = true;
        (*it).first = sz;
        new_node(pt, tch);
      }
      pt = (*it).first;
    }
    words[pt].push_back(pt_string.size());
    pt_string.push_back(pt);
  }
  void build_link_tree() {
    ok_link_tree = true;
    glink.resize(sz);
    for (long long i = 1; i < sz; i++) {
      glink[get_link(i)].push_back(i);
    }
  }
  void build_match() {
    ok_match = true;
    if (ok_link_tree == false) build_link_tree();
    vtime.resize(sz);
    lim.resize(sz);
    abi.resize(sz + 1);
    long long ct = 0;
    function<void(long long)> DFS = [&](long long nodo) {
      vtime[nodo] = ++ct;
      for (auto v : glink[nodo]) {
        DFS(v);
      }
      lim[nodo] = {vtime[nodo], ct};
    };
    DFS(0);
  }
  void abi_update(long long x, long long v) {
    while (x < abi.size()) {
      abi[x] += v;
      x += x & -x;
    }
  }
  long long abi_query(long long x) {
    long long res = 0;
    while (x) {
      res += abi[x];
      x -= x & -x;
    }
    return res;
  }
  long long abi_range(long long a, long long b) {
    return abi_query(b) - abi_query(a - 1);
  }
  vector<long long> match(vector<T> vcad) {
    if (ok_match == false) build_match();
    vector<long long> ups;
    for (auto cad : vcad) {
      long long pt = 0;
      for (long long i = 0; i < cad.size(); i++) {
        pt = go(pt, cad[i]);
        abi_update(vtime[pt], 1);
        ups.push_back(vtime[pt]);
      }
    }
    vector<long long> res(pt_string.size());
    for (long long i = 0; i < pt_string.size(); i++) {
      res[i] = abi_range(lim[pt_string[i]].first, lim[pt_string[i]].second);
    }
    for (auto x : ups) {
      abi_update(x, -1);
    }
    return res;
  }
  vector<long long> match_offline(vector<T> vcad) {
    if (ok_link_tree == false) build_link_tree();
    vector<long long> dp(sz);
    for (auto cad : vcad) {
      long long pt = 0;
      for (long long i = 0; i < cad.size(); i++) {
        pt = go(pt, cad[i]);
        dp[pt]++;
      }
    }
    function<void(long long)> DFS = [&](long long nodo) {
      for (auto v : glink[nodo]) {
        DFS(v);
        dp[nodo] += dp[v];
      }
    };
    DFS(0);
    vector<long long> res(pt_string.size());
    for (long long i = 0; i < pt_string.size(); i++) {
      res[i] = dp[pt_string[i]];
    }
    return res;
  }
  long long get_dictionary_link(long long nodo) {
    if (dict_link[nodo] == -1) {
      if (nodo == 0 || p[nodo] == 0)
        dict_link[nodo] = 0;
      else {
        long long v = get_link(nodo);
        if (words[v].size())
          dict_link[nodo] = v;
        else
          dict_link[nodo] = get_dictionary_link(v);
      }
    }
    return dict_link[nodo];
  }
  long long get_link(long long nodo) {
    if (link[nodo] == -1) {
      if (nodo == 0 || p[nodo] == 0)
        link[nodo] = 0;
      else
        link[nodo] = go(get_link(p[nodo]), ch[nodo]);
    }
    return link[nodo];
  }
  long long go(long long nodo, F tch) {
    auto it = &tgo[nodo][tch];
    if ((*it).second == false) {
      (*it).second = true;
      (*it).first = (nodo == 0) ? 0 : go(get_link(nodo), tch);
    }
    return (*it).first;
  }
};
const long long MAXN = 2e5 + 100;
long long arr1[MAXN];
long long arr2[MAXN];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  AHO_CORASICK<string, char> AC1;
  AHO_CORASICK<string, char> AC2;
  string T;
  cin >> T;
  long long N;
  cin >> N;
  for (long long i = 0; i < N; i++) {
    string cad;
    cin >> cad;
    AC1.add_string(cad);
    reverse(cad.begin(), cad.end());
    AC2.add_string(cad);
  }
  AC1.build_link_tree();
  AC2.build_link_tree();
  vector<long long> cant1(AC1.size());
  vector<long long> cant2(AC2.size());
  for (auto x : AC1.pt_string) {
    cant1[x]++;
  }
  for (auto x : AC2.pt_string) {
    cant2[x]++;
  }
  function<void(long long)> DFS1 = [&](long long nodo) {
    for (auto v : AC1.glink[nodo]) {
      cant1[v] += cant1[nodo];
      DFS1(v);
    }
  };
  DFS1(0);
  function<void(long long)> DFS2 = [&](long long nodo) {
    for (auto v : AC2.glink[nodo]) {
      cant2[v] += cant2[nodo];
      DFS2(v);
    }
  };
  DFS2(0);
  long long pt = 0;
  for (long long i = 0; i < T.size(); i++) {
    pt = AC1.go(pt, T[i]);
    arr1[i] = cant1[pt];
  }
  pt = 0;
  for (long long i = T.size() - 1; i >= 0; i--) {
    pt = AC2.go(pt, T[i]);
    arr2[i] = cant2[pt];
  }
  long long res = 0;
  for (long long i = 0; i < T.size() - 1; i++) {
    res += arr1[i] * arr2[i + 1];
  }
  cout << res << '\n';
  return 0;
}

```