#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = 0;
  int x = 0, flag = 1;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') flag = -1;
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * flag;
}
int root = 1, size = 1, last = 1;
struct node {
  int len, lnk, nxt[26];
} s[220000];
void build(int k) {
  int cur = ++size, p = last;
  last = cur;
  s[cur].len = s[p].len + 1;
  while (p && !s[p].nxt[k]) s[p].nxt[k] = cur, p = s[p].lnk;
  if (!p) {
    s[cur].lnk = root;
    return;
  }
  int q = s[p].nxt[k];
  if (s[q].len == s[p].len + 1) {
    s[cur].lnk = q;
    return;
  } else {
    int clone = ++size;
    s[clone] = s[q];
    s[clone].len = s[p].len + 1;
    while (p && s[p].nxt[k] == q) s[p].nxt[k] = clone, p = s[p].lnk;
    s[q].lnk = s[cur].lnk = clone;
  }
}
char ch[220000];
bool flag[220000];
vector<int> v[220000];
int p[220000], f[220000], L[220000], R[220000], dp[220000];
bool cmp(int a, int b) { return s[a].len < s[b].len; }
int main() {
  scanf("%s", ch + 1);
  int n = strlen(ch + 1);
  for (int i = 1; i <= n; i++) build(ch[i] - 'a'), dp[last] = 1;
  for (int i = 1; i <= size; i++)
    p[i] = i, L[i] = s[s[i].lnk].len + 1, R[i] = s[i].len, flag[i] = true;
  sort(p + 1, p + size + 1, cmp);
  int m = read();
  for (int o = 1; o <= m; o++) {
    scanf("%s", ch + 1);
    int len = strlen(ch + 1), l = read(), r = read();
    for (int i = 1, x = root, t = 0; i <= len; i++) {
      int k = ch[i] - 'a';
      if (!s[x].nxt[k]) {
        while (x && !s[x].nxt[k]) x = s[x].lnk;
        t = s[x].len;
        if (!x) {
          x = root;
          t = 0;
          continue;
        }
      }
      x = s[x].nxt[k];
      t++;
      if (t != s[x].len)
        v[x].push_back(t);
      else
        f[x]++;
    }
    for (int i = size; i >= 1; i--) {
      int x = p[i], cnt = v[x].size();
      sort(v[x].begin(), v[x].end());
      f[s[x].lnk] += f[x] + cnt;
      int j = -1, tot = f[x] + cnt, lk = 1e8 + 7, rk = -1e8 + 7;
      if (l <= tot && tot <= r)
        lk = min(lk, s[s[x].lnk].len + 1), rk = max(rk, s[s[x].lnk].len + 1);
      while (j != cnt - 1) {
        j++;
        if (l <= tot && tot <= r) lk = min(lk, v[x][j]), rk = max(rk, v[x][j]);
        while (j != cnt - 1 && v[x][j + 1] == v[x][j]) j++, tot--;
        tot--;
      }
      if (l <= tot && tot <= r) lk = min(lk, s[x].len), rk = max(rk, s[x].len);
      lk = max(lk, s[s[x].lnk].len + 1);
      L[x] = max(L[x], lk);
      R[x] = min(R[x], rk);
      v[x].clear();
      f[x] = 0;
    }
  }
  long long ans = 0;
  for (int i = 1; i <= size; i++) ans += max(0, R[i] - L[i] + 1);
  printf("%lld", ans);
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

Smart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some string s. To determine if a string is good or not the game uses rules. Overall there are n rules. Each rule is described by a group of three (p, l, r), where p is a string and l and r (l ≤ r) are integers. We’ll say that string t complies with rule (p, l, r), if the number of occurrences of string t in string p lies between l and r, inclusive. For example, string "ab", complies with rules ("ab", 1, 2) and ("aab", 0, 1), but does not comply with rules ("cd", 1, 2) and ("abab", 0, 1).

A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s1s2... s|s| (|s| is a length of s) is string slsl + 1... sr.

Consider a number of occurrences  of string t in string p as a number of pairs of integers l, r (1 ≤ l ≤ r ≤ |p|) such that p[l... r] = t.

We’ll say that string t is good if it complies with all n rules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of string s. Two substrings s[x... y] and s[z... w] are cosidered to be distinct iff s[x... y] ≠ s[z... w].

Input

The first line contains string s. The second line contains integer n. Next n lines contain the rules, one per line. Each of these lines contains a string and two integers pi, li, ri, separated by single spaces (0 ≤ li ≤ ri ≤ |pi|). It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.

The input limits for scoring 30 points are (subproblem G1): 

  * 0 ≤ n ≤ 10. 
  * The length of string s and the maximum length of string p is  ≤ 200. 



The input limits for scoring 70 points are (subproblems G1+G2): 

  * 0 ≤ n ≤ 10. 
  * The length of string s and the maximum length of string p is  ≤ 2000. 



The input limits for scoring 100 points are (subproblems G1+G2+G3): 

  * 0 ≤ n ≤ 10. 
  * The length of string s and the maximum length of string p is  ≤ 50000. 

Output

Print a single integer — the number of good substrings of string s.

Examples

Input

aaab
2
aa 0 0
aab 1 1


Output

3


Input

ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1


Output

2


Input

a
0


Output

1

Note

There are three good substrings in the first sample test: «aab», «ab» and «b».

In the second test only substrings «e» and «t» are good.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = 0;
  int x = 0, flag = 1;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') flag = -1;
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * flag;
}
int root = 1, size = 1, last = 1;
struct node {
  int len, lnk, nxt[26];
} s[220000];
void build(int k) {
  int cur = ++size, p = last;
  last = cur;
  s[cur].len = s[p].len + 1;
  while (p && !s[p].nxt[k]) s[p].nxt[k] = cur, p = s[p].lnk;
  if (!p) {
    s[cur].lnk = root;
    return;
  }
  int q = s[p].nxt[k];
  if (s[q].len == s[p].len + 1) {
    s[cur].lnk = q;
    return;
  } else {
    int clone = ++size;
    s[clone] = s[q];
    s[clone].len = s[p].len + 1;
    while (p && s[p].nxt[k] == q) s[p].nxt[k] = clone, p = s[p].lnk;
    s[q].lnk = s[cur].lnk = clone;
  }
}
char ch[220000];
bool flag[220000];
vector<int> v[220000];
int p[220000], f[220000], L[220000], R[220000], dp[220000];
bool cmp(int a, int b) { return s[a].len < s[b].len; }
int main() {
  scanf("%s", ch + 1);
  int n = strlen(ch + 1);
  for (int i = 1; i <= n; i++) build(ch[i] - 'a'), dp[last] = 1;
  for (int i = 1; i <= size; i++)
    p[i] = i, L[i] = s[s[i].lnk].len + 1, R[i] = s[i].len, flag[i] = true;
  sort(p + 1, p + size + 1, cmp);
  int m = read();
  for (int o = 1; o <= m; o++) {
    scanf("%s", ch + 1);
    int len = strlen(ch + 1), l = read(), r = read();
    for (int i = 1, x = root, t = 0; i <= len; i++) {
      int k = ch[i] - 'a';
      if (!s[x].nxt[k]) {
        while (x && !s[x].nxt[k]) x = s[x].lnk;
        t = s[x].len;
        if (!x) {
          x = root;
          t = 0;
          continue;
        }
      }
      x = s[x].nxt[k];
      t++;
      if (t != s[x].len)
        v[x].push_back(t);
      else
        f[x]++;
    }
    for (int i = size; i >= 1; i--) {
      int x = p[i], cnt = v[x].size();
      sort(v[x].begin(), v[x].end());
      f[s[x].lnk] += f[x] + cnt;
      int j = -1, tot = f[x] + cnt, lk = 1e8 + 7, rk = -1e8 + 7;
      if (l <= tot && tot <= r)
        lk = min(lk, s[s[x].lnk].len + 1), rk = max(rk, s[s[x].lnk].len + 1);
      while (j != cnt - 1) {
        j++;
        if (l <= tot && tot <= r) lk = min(lk, v[x][j]), rk = max(rk, v[x][j]);
        while (j != cnt - 1 && v[x][j + 1] == v[x][j]) j++, tot--;
        tot--;
      }
      if (l <= tot && tot <= r) lk = min(lk, s[x].len), rk = max(rk, s[x].len);
      lk = max(lk, s[s[x].lnk].len + 1);
      L[x] = max(L[x], lk);
      R[x] = min(R[x], rk);
      v[x].clear();
      f[x] = 0;
    }
  }
  long long ans = 0;
  for (int i = 1; i <= size; i++) ans += max(0, R[i] - L[i] + 1);
  printf("%lld", ans);
  return 0;
}

```