#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <int n, class... T>
typename std::enable_if<(n >= sizeof...(T))>::type __output_tuple(
    std::ostream &, std::tuple<T...> const &) {}
template <int n, class... T>
typename std::enable_if<(n < sizeof...(T))>::type __output_tuple(
    std::ostream &os, std::tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << std::get<n>(t);
  __output_tuple<n + 1>(os, t);
}
template <class... T>
std::ostream &operator<<(std::ostream &os, std::tuple<T...> const &t) {
  os << "(";
  __output_tuple<0>(os, t);
  os << ")";
  return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::stack<T> &a) {
  os << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template <class T, class Container, class Compare>
std::ostream &operator<<(std::ostream &os,
                         std::priority_queue<T, Container, Compare> a) {
  os << "{ (top) ";
  while (a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T, class Container>
std::ostream &operator<<(std::ostream &os, std::queue<T, Container> a) {
  os << "{ ";
  while (a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <
    class T,
    class = typename std::iterator_traits<decltype(begin(T()))>::value_type,
    class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::ostream &operator<<(std::ostream &os, const T &a) {
  for (auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
struct AhoCorasick {
  struct Trie {
    unordered_map<char, Trie *> child;
    int id;
    Trie *failure = nullptr;
    Trie *next = nullptr;
    int word = -1;
    Trie *add(char c) {
      if (child.count(c)) {
        return child[c];
      } else {
        return child[c] = new Trie;
      }
    }
    Trie *go(char c) {
      if (child.count(c)) {
        return child[c];
      } else {
        if (failure == nullptr) {
          return this;
        } else {
          return failure->go(c);
        }
      }
    }
    ~Trie() {
      for (auto &x : child) {
        delete x.second;
      }
    }
  };
  Trie *top = new Trie;
  ~AhoCorasick() {}
  vector<string> dict;
  void add(string word) {
    Trie *now = top;
    for (size_t i = 0; i < word.size(); i++) {
      now = now->add(word[i]);
    }
    now->word = dict.size();
    dict.emplace_back(word);
  }
  void build() {
    queue<Trie *> q;
    q.emplace(top);
    while (q.size()) {
      Trie *now = q.front();
      q.pop();
      for (pair<char, Trie *> ch : now->child) {
        q.emplace(ch.second);
        Trie *failure = ch.second->failure =
            now == top ? top : now->failure->go(ch.first);
        ch.second->next = failure->word >= 0 ? failure : failure->next;
      }
    }
  }
  Trie *next(
      Trie *now, char c, const function<void(int, int)> &f = [](int, int) {}) {
    now = now->go(c);
    Trie *tmp = now;
    while (tmp != nullptr && tmp != top) {
      int word = tmp->word;
      if (word >= 0) {
        f(dict[word].size(), word);
      }
      tmp = tmp->next;
    }
    return now;
  }
  void match(
      string s, const function<void(int, int, int)> &f = [](int, int, int) {}) {
    Trie *now = top;
    for (size_t i = 0; i < s.size(); i++) {
      now = now->go(s[i]);
      Trie *tmp = now;
      while (tmp != nullptr && tmp != top) {
        int word = tmp->word;
        if (word >= 0) {
          f(i - dict[word].size() + 1, i, word);
        }
        tmp = tmp->next;
      }
    }
  }
};
using Trie = AhoCorasick::Trie;
int n;
string s[212345];
constexpr int inf = 1e9;
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  string t;
  cin >> t;
  cin >> n;
  int T = t.size();
  AhoCorasick aho;
  map<string, int> cnt;
  for (int i = 0; i < n; i++) cin >> s[i], cnt[s[i]]++;
  vector<int> num;
  for (auto p : cnt) aho.add(p.first), num.push_back(p.second);
  aho.build();
  vector<ll> L(T), R(T);
  Trie *now = aho.top;
  for (int i = 0; i < T; i++) {
    now = aho.next(now, t[i], [&](int len, int key) {
      L[i - len + 1] += num[key];
      R[i] += num[key];
    });
  }
  ll ans = 0;
  for (int i = 0; i < T - 1; i++) ans += R[i] * L[i + 1];
  cout << ans << endl;
  return 0;
}

### 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;
using ll = long long;
template <int n, class... T>
typename std::enable_if<(n >= sizeof...(T))>::type __output_tuple(
    std::ostream &, std::tuple<T...> const &) {}
template <int n, class... T>
typename std::enable_if<(n < sizeof...(T))>::type __output_tuple(
    std::ostream &os, std::tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << std::get<n>(t);
  __output_tuple<n + 1>(os, t);
}
template <class... T>
std::ostream &operator<<(std::ostream &os, std::tuple<T...> const &t) {
  os << "(";
  __output_tuple<0>(os, t);
  os << ")";
  return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::stack<T> &a) {
  os << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template <class T, class Container, class Compare>
std::ostream &operator<<(std::ostream &os,
                         std::priority_queue<T, Container, Compare> a) {
  os << "{ (top) ";
  while (a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T, class Container>
std::ostream &operator<<(std::ostream &os, std::queue<T, Container> a) {
  os << "{ ";
  while (a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <
    class T,
    class = typename std::iterator_traits<decltype(begin(T()))>::value_type,
    class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::ostream &operator<<(std::ostream &os, const T &a) {
  for (auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
struct AhoCorasick {
  struct Trie {
    unordered_map<char, Trie *> child;
    int id;
    Trie *failure = nullptr;
    Trie *next = nullptr;
    int word = -1;
    Trie *add(char c) {
      if (child.count(c)) {
        return child[c];
      } else {
        return child[c] = new Trie;
      }
    }
    Trie *go(char c) {
      if (child.count(c)) {
        return child[c];
      } else {
        if (failure == nullptr) {
          return this;
        } else {
          return failure->go(c);
        }
      }
    }
    ~Trie() {
      for (auto &x : child) {
        delete x.second;
      }
    }
  };
  Trie *top = new Trie;
  ~AhoCorasick() {}
  vector<string> dict;
  void add(string word) {
    Trie *now = top;
    for (size_t i = 0; i < word.size(); i++) {
      now = now->add(word[i]);
    }
    now->word = dict.size();
    dict.emplace_back(word);
  }
  void build() {
    queue<Trie *> q;
    q.emplace(top);
    while (q.size()) {
      Trie *now = q.front();
      q.pop();
      for (pair<char, Trie *> ch : now->child) {
        q.emplace(ch.second);
        Trie *failure = ch.second->failure =
            now == top ? top : now->failure->go(ch.first);
        ch.second->next = failure->word >= 0 ? failure : failure->next;
      }
    }
  }
  Trie *next(
      Trie *now, char c, const function<void(int, int)> &f = [](int, int) {}) {
    now = now->go(c);
    Trie *tmp = now;
    while (tmp != nullptr && tmp != top) {
      int word = tmp->word;
      if (word >= 0) {
        f(dict[word].size(), word);
      }
      tmp = tmp->next;
    }
    return now;
  }
  void match(
      string s, const function<void(int, int, int)> &f = [](int, int, int) {}) {
    Trie *now = top;
    for (size_t i = 0; i < s.size(); i++) {
      now = now->go(s[i]);
      Trie *tmp = now;
      while (tmp != nullptr && tmp != top) {
        int word = tmp->word;
        if (word >= 0) {
          f(i - dict[word].size() + 1, i, word);
        }
        tmp = tmp->next;
      }
    }
  }
};
using Trie = AhoCorasick::Trie;
int n;
string s[212345];
constexpr int inf = 1e9;
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  string t;
  cin >> t;
  cin >> n;
  int T = t.size();
  AhoCorasick aho;
  map<string, int> cnt;
  for (int i = 0; i < n; i++) cin >> s[i], cnt[s[i]]++;
  vector<int> num;
  for (auto p : cnt) aho.add(p.first), num.push_back(p.second);
  aho.build();
  vector<ll> L(T), R(T);
  Trie *now = aho.top;
  for (int i = 0; i < T; i++) {
    now = aho.next(now, t[i], [&](int len, int key) {
      L[i - len + 1] += num[key];
      R[i] += num[key];
    });
  }
  ll ans = 0;
  for (int i = 0; i < T - 1; i++) ans += R[i] * L[i + 1];
  cout << ans << endl;
  return 0;
}

```