#include <bits/stdc++.h>
template <class... Args>
inline __attribute__((always_inline)) void read(Args&... args) {
  (std::cin >> ... >> args);
}
template <class... Args>
inline __attribute__((always_inline)) void write(Args&&... args) {
  (std::cout << ... << std::forward<Args>(args));
}
template <class... Args>
inline __attribute__((always_inline)) void writeln(Args&&... args) {
  write(std::forward<Args>(args)..., '\n');
}
inline __attribute__((always_inline)) void flush_write() {
  std::flush(std::cout);
}
constexpr int ALPH_SZ = 'z' - 'a' + 1;
class aho_corasick {
  struct node_t {
    int next[ALPH_SZ];
    int p;
    char cp;
    int link;
    int cnt;
  };
  std::vector<node_t> nodes;
  int new_node(int p, char cp) {
    int ind = nodes.size();
    nodes.emplace_back();
    auto& nn = nodes.back();
    std::fill(std::begin(nn.next), std::end(nn.next), -1);
    nn.p = p;
    nn.cp = cp;
    nn.link = -1;
    nn.cnt = 0;
    return ind;
  }
  int trie_go(int it, char ch) {
    assert(it != -1);
    assert(0 <= ch && ch < ALPH_SZ);
    int r = nodes[it].next[(int)ch];
    if (r == -1) {
      r = new_node(it, ch);
      nodes[it].next[(int)ch] = r;
    }
    return r;
  }
  int link(int v) {
    assert(v != -1);
    auto& it = nodes[v];
    if (it.link == -1) {
      it.link = it.p ? go(link(it.p), it.cp) : 0;
      it.cnt += cnt(it.link);
    }
    return it.link;
  }
  int cnt(int v) {
    assert(v != -1);
    link(v);
    return nodes[v].cnt;
  }
  int go(int v, char ch) {
    assert(v != -1);
    assert(0 <= ch && ch < ALPH_SZ);
    while (v && nodes[v].next[(int)ch] == -1) v = link(v);
    int nxt = nodes[v].next[(int)ch];
    if (nxt != -1) return nxt;
    assert(v == 0);
    return v;
  }

 public:
  explicit aho_corasick(const std::vector<std::string>& ss) {
    {
      int root = new_node(0, 0);
      assert(0 == root);
    }
    for (auto& s : ss) {
      int it = 0;
      for (auto ch : s) it = trie_go(it, ch - 'a');
      nodes[it].cnt += 1;
    }
    for (int pi = 1; pi < (int)nodes.size(); ++pi) nodes[pi].link = link(pi);
  }
  std::vector<int> cnt_ends(const std::string& t) {
    int n = t.length();
    std::vector<int> res(n + 1);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
      cur = go(cur, t[i] - 'a');
      res[i + 1] = cnt(cur);
    }
    return res;
  }
};
std::vector<int> cnt_ends(const std::string& t,
                          const std::vector<std::string>& ss) {
  return aho_corasick(ss).cnt_ends(t);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::fixed(std::cout).precision(20);
  std::cin.exceptions(std::ios_base::failbit);
  std::cin.tie(nullptr);
  std::string t;
  read(t);
  int n;
  read(n);
  std::vector<std::string> ss(n);
  for (auto& s : ss) read(s);
  auto nd_cnt = cnt_ends(t, ss);
  std::reverse(t.begin(), t.end());
  for (auto& s : ss) std::reverse(s.begin(), s.end());
  auto bg_cnt = cnt_ends(t, ss);
  std::reverse(bg_cnt.begin(), bg_cnt.end());
  int64_t res = 0;
  for (int i = 1; i < (int)t.length(); ++i) {
    res += (int64_t)bg_cnt[i] * nd_cnt[i];
  }
  writeln(res);
  return 0;
}

### Prompt

Your task is to create a cpp solution 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>
template <class... Args>
inline __attribute__((always_inline)) void read(Args&... args) {
  (std::cin >> ... >> args);
}
template <class... Args>
inline __attribute__((always_inline)) void write(Args&&... args) {
  (std::cout << ... << std::forward<Args>(args));
}
template <class... Args>
inline __attribute__((always_inline)) void writeln(Args&&... args) {
  write(std::forward<Args>(args)..., '\n');
}
inline __attribute__((always_inline)) void flush_write() {
  std::flush(std::cout);
}
constexpr int ALPH_SZ = 'z' - 'a' + 1;
class aho_corasick {
  struct node_t {
    int next[ALPH_SZ];
    int p;
    char cp;
    int link;
    int cnt;
  };
  std::vector<node_t> nodes;
  int new_node(int p, char cp) {
    int ind = nodes.size();
    nodes.emplace_back();
    auto& nn = nodes.back();
    std::fill(std::begin(nn.next), std::end(nn.next), -1);
    nn.p = p;
    nn.cp = cp;
    nn.link = -1;
    nn.cnt = 0;
    return ind;
  }
  int trie_go(int it, char ch) {
    assert(it != -1);
    assert(0 <= ch && ch < ALPH_SZ);
    int r = nodes[it].next[(int)ch];
    if (r == -1) {
      r = new_node(it, ch);
      nodes[it].next[(int)ch] = r;
    }
    return r;
  }
  int link(int v) {
    assert(v != -1);
    auto& it = nodes[v];
    if (it.link == -1) {
      it.link = it.p ? go(link(it.p), it.cp) : 0;
      it.cnt += cnt(it.link);
    }
    return it.link;
  }
  int cnt(int v) {
    assert(v != -1);
    link(v);
    return nodes[v].cnt;
  }
  int go(int v, char ch) {
    assert(v != -1);
    assert(0 <= ch && ch < ALPH_SZ);
    while (v && nodes[v].next[(int)ch] == -1) v = link(v);
    int nxt = nodes[v].next[(int)ch];
    if (nxt != -1) return nxt;
    assert(v == 0);
    return v;
  }

 public:
  explicit aho_corasick(const std::vector<std::string>& ss) {
    {
      int root = new_node(0, 0);
      assert(0 == root);
    }
    for (auto& s : ss) {
      int it = 0;
      for (auto ch : s) it = trie_go(it, ch - 'a');
      nodes[it].cnt += 1;
    }
    for (int pi = 1; pi < (int)nodes.size(); ++pi) nodes[pi].link = link(pi);
  }
  std::vector<int> cnt_ends(const std::string& t) {
    int n = t.length();
    std::vector<int> res(n + 1);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
      cur = go(cur, t[i] - 'a');
      res[i + 1] = cnt(cur);
    }
    return res;
  }
};
std::vector<int> cnt_ends(const std::string& t,
                          const std::vector<std::string>& ss) {
  return aho_corasick(ss).cnt_ends(t);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::fixed(std::cout).precision(20);
  std::cin.exceptions(std::ios_base::failbit);
  std::cin.tie(nullptr);
  std::string t;
  read(t);
  int n;
  read(n);
  std::vector<std::string> ss(n);
  for (auto& s : ss) read(s);
  auto nd_cnt = cnt_ends(t, ss);
  std::reverse(t.begin(), t.end());
  for (auto& s : ss) std::reverse(s.begin(), s.end());
  auto bg_cnt = cnt_ends(t, ss);
  std::reverse(bg_cnt.begin(), bg_cnt.end());
  int64_t res = 0;
  for (int i = 1; i < (int)t.length(); ++i) {
    res += (int64_t)bg_cnt[i] * nd_cnt[i];
  }
  writeln(res);
  return 0;
}

```