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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int K = 26;
const int NMAX = 4e5;
struct info_t {
  int len = 0;
  long long c = 0;
  long long endc = -1;
  info_t() {}
};
struct vertex {
  int next[K];
  int next_term = -1;
  bool leaf;
  int p;
  char pch;
  int link;
  int go[K];
  info_t info;
  vertex() : link(-1), p(-1), pch(-1), leaf(false) {
    fill(go, go + K, -1);
    fill(next, next + K, -1);
  }
};
static vector<vertex> t(NMAX + 1);
int sz;
void init() {
  t.assign(NMAX + 1, vertex());
  t[0].p = t[0].link = -1;
  t[0].info.endc = 0;
  t[0].next_term = 0;
  sz = 1;
}
void add_string(const string& s) {
  int v = 0;
  for (size_t i = 0; i < s.length(); ++i) {
    char c = s[i] - 'a';
    if (t[v].next[c] == -1) {
      t[sz].link = -1;
      t[sz].p = v;
      t[sz].pch = c;
      t[v].next[c] = sz++;
    }
    v = t[v].next[c];
  }
  t[v].info.len = s.size();
  t[v].info.c++;
  t[v].leaf = true;
}
int go(int v, char c);
int get_link(int v) {
  if (t[v].link == -1) {
    if (v == 0 || t[v].p == 0) {
      t[v].link = 0;
    } else {
      t[v].link = go(get_link(t[v].p), t[v].pch);
    }
  }
  return t[v].link;
}
int go(int v, char c) {
  if (t[v].go[c] == -1) {
    if (t[v].next[c] != -1) {
      t[v].go[c] = t[v].next[c];
    } else {
      t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
    }
  }
  return t[v].go[c];
}
int next_term(int v) {
  if (t[v].next_term == -1) {
    int link = get_link(v);
    if (t[link].leaf) {
      t[v].next_term = link;
    } else {
      t[v].next_term = next_term(link);
    }
  }
  return t[v].next_term;
}
long long sol2(string& text) {
  vector<long long> st(text.size());
  vector<long long> ed(text.size());
  int v = 0;
  for (int i = 0; i < text.size(); i++) {
    v = go(v, text[i] - 'a');
    int u = t[v].leaf ? v : next_term(v);
    while (u != 0) {
      ed[i] += t[u].info.c;
      st[i - t[u].info.len + 1] += t[u].info.c;
      u = next_term(u);
    }
  }
  long long res = 0;
  for (int i = 0; i < text.size() - 1; i++) {
    res += ed[i] * st[i + 1];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  srand(123);
  string text(10, 'a');
  while (cin >> text) {
    int n = 2;
    cin >> n;
    init();
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
      cin >> s[i];
      add_string(s[i]);
    }
    for (int i = 0; i < sz; i++) {
    }
    std::function<long long(int)> calc_ends = [&](int v) -> long long {
      if (::t[v].info.endc == -1) {
        ::t[v].info.endc = calc_ends(get_link(v)) + ::t[v].info.c;
      }
      return ::t[v].info.endc;
    };
    vector<long long> efw(text.size());
    vector<long long> ebw(text.size());
    int v = 0;
    for (int i = 0; i < text.size(); i++) {
      v = go(v, text[i] - 'a');
      efw[i] = calc_ends(v);
    }
    cout << endl;
    init();
    for (int i = 0; i < n; i++) {
      reverse(s[i].begin(), s[i].end());
      add_string(s[i]);
    }
    v = 0;
    for (int i = text.size() - 1; i >= 0; i--) {
      v = go(v, text[i] - 'a');
      ebw[i] = calc_ends(v);
    }
    long long ans = 0;
    for (int i = 0; i < text.size() - 1; i++) {
      ans += efw[i] * ebw[i + 1];
    }
    cout << ans << endl;
  }
}