#include <bits/stdc++.h>
using namespace std;
long long n, m, x, sum, p[200005], f[200005];
char s[200005], c[200005];
queue<long long> Q;
struct tree {
  struct node {
    long long next, to;
  } a[200005];
  long long tot = 0, cnt = 0, rt, ch[200005][26], fail[200005], fa[200005],
            v[200005], sum[200005];
  long long head[200005];
  void add(long long u, long long v) {
    a[++tot].next = head[u];
    a[tot].to = v;
    head[u] = tot;
  }
  void read() {
    rt = 0;
    for (long long i = 1; i <= x; i++) {
      if (ch[rt][c[i] - 'a'])
        rt = ch[rt][c[i] - 'a'];
      else {
        ch[rt][c[i] - 'a'] = ++cnt;
        fa[cnt] = rt;
        rt = cnt;
      }
    }
    v[rt]++;
  }
  void build() {
    for (long long i = 0; i <= 25; i++)
      if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
      long long u = Q.front();
      Q.pop();
      add(fail[u], u);
      for (long long i = 0; i <= 25; i++)
        if (ch[u][i])
          fail[ch[u][i]] = ch[fail[u]][i], Q.push(ch[u][i]);
        else
          ch[u][i] = ch[fail[u]][i];
    }
  }
  void dfs(long long u) {
    sum[u] += v[u];
    for (long long i = head[u]; i; i = a[i].next) {
      sum[a[i].to] = sum[u];
      dfs(a[i].to);
    }
  }
} t1, t2;
void init() {
  scanf("%s", c + 1);
  x = strlen(c + 1);
  t1.read();
  for (long long i = 1; i <= x >> 1; i++) swap(c[i], c[x - i + 1]);
  t2.read();
}
void work1() {
  t1.rt = 0;
  for (long long i = 1; i <= n; i++) {
    if (t1.ch[t1.rt][s[i] - 'a'])
      t1.rt = t1.ch[t1.rt][s[i] - 'a'];
    else
      t1.rt = t1.ch[t1.fail[t1.rt]][s[i] - 'a'];
    p[i] = t1.sum[t1.rt];
  }
}
void work2() {
  t2.rt = 0;
  for (long long i = n; i >= 1; i--) {
    if (t2.ch[t2.rt][s[i] - 'a'])
      t2.rt = t2.ch[t2.rt][s[i] - 'a'];
    else
      t2.rt = t2.ch[t2.fail[t2.rt]][s[i] - 'a'];
    f[i] = t2.sum[t2.rt];
  }
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  scanf("%lld", &m);
  for (long long i = 1; i <= m; i++) init();
  t1.build();
  t1.dfs(0);
  t2.build();
  t2.dfs(0);
  work1();
  work2();
  for (long long i = 1; i <= n; i++) sum += p[i] * f[i + 1];
  printf("%lld", sum);
  return 0;
}

### Prompt

Develop a solution in cpp 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;
long long n, m, x, sum, p[200005], f[200005];
char s[200005], c[200005];
queue<long long> Q;
struct tree {
  struct node {
    long long next, to;
  } a[200005];
  long long tot = 0, cnt = 0, rt, ch[200005][26], fail[200005], fa[200005],
            v[200005], sum[200005];
  long long head[200005];
  void add(long long u, long long v) {
    a[++tot].next = head[u];
    a[tot].to = v;
    head[u] = tot;
  }
  void read() {
    rt = 0;
    for (long long i = 1; i <= x; i++) {
      if (ch[rt][c[i] - 'a'])
        rt = ch[rt][c[i] - 'a'];
      else {
        ch[rt][c[i] - 'a'] = ++cnt;
        fa[cnt] = rt;
        rt = cnt;
      }
    }
    v[rt]++;
  }
  void build() {
    for (long long i = 0; i <= 25; i++)
      if (ch[0][i]) Q.push(ch[0][i]);
    while (!Q.empty()) {
      long long u = Q.front();
      Q.pop();
      add(fail[u], u);
      for (long long i = 0; i <= 25; i++)
        if (ch[u][i])
          fail[ch[u][i]] = ch[fail[u]][i], Q.push(ch[u][i]);
        else
          ch[u][i] = ch[fail[u]][i];
    }
  }
  void dfs(long long u) {
    sum[u] += v[u];
    for (long long i = head[u]; i; i = a[i].next) {
      sum[a[i].to] = sum[u];
      dfs(a[i].to);
    }
  }
} t1, t2;
void init() {
  scanf("%s", c + 1);
  x = strlen(c + 1);
  t1.read();
  for (long long i = 1; i <= x >> 1; i++) swap(c[i], c[x - i + 1]);
  t2.read();
}
void work1() {
  t1.rt = 0;
  for (long long i = 1; i <= n; i++) {
    if (t1.ch[t1.rt][s[i] - 'a'])
      t1.rt = t1.ch[t1.rt][s[i] - 'a'];
    else
      t1.rt = t1.ch[t1.fail[t1.rt]][s[i] - 'a'];
    p[i] = t1.sum[t1.rt];
  }
}
void work2() {
  t2.rt = 0;
  for (long long i = n; i >= 1; i--) {
    if (t2.ch[t2.rt][s[i] - 'a'])
      t2.rt = t2.ch[t2.rt][s[i] - 'a'];
    else
      t2.rt = t2.ch[t2.fail[t2.rt]][s[i] - 'a'];
    f[i] = t2.sum[t2.rt];
  }
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  scanf("%lld", &m);
  for (long long i = 1; i <= m; i++) init();
  t1.build();
  t1.dfs(0);
  t2.build();
  t2.dfs(0);
  work1();
  work2();
  for (long long i = 1; i <= n; i++) sum += p[i] * f[i + 1];
  printf("%lld", sum);
  return 0;
}

```