#include <bits/stdc++.h>
using namespace std;
const int MAXP = 2000 + 100;
int t[MAXP], c[MAXP], r[MAXP];
struct SuffixArray {
  char T[MAXP];
  int p[MAXP], n;
  void countSort(int k) {
    int m = max(255, n), i;
    for (i = 0; i <= m; ++i) c[i] = 0;
    for (i = 0; i < n; ++i) c[((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0)]++;
    for (i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--)
      t[--c[((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0)]] = p[i];
    for (i = 0; i < n; ++i) p[i] = t[i];
  }
  void buildSA() {
    n = strlen(T);
    T[n++] = '$';
    T[n] = '\0';
    for (int i = 0; i < n; ++i) {
      r[i] = T[i];
      p[i] = i;
    }
    int f, i;
    for (int k = 1; k < n; k *= 2) {
      countSort(k);
      countSort(0);
      f = t[p[0]] = 0;
      for (i = 1; i < n; ++i) {
        t[p[i]] = (((p[i] + (0)) < (n) ? (r[p[i] + (0)]) : 0) ==
                       ((p[i - 1] + (0)) < (n) ? (r[p[i - 1] + (0)]) : 0) &&
                   ((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0) ==
                       ((p[i - 1] + (k)) < (n) ? (r[p[i - 1] + (k)]) : 0))
                      ? f
                      : ++f;
      }
      for (i = 0; i < n; ++i) r[i] = t[i];
      if (f == n - 1) break;
    }
  }
  int findLowerBound(char* S, int m) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (strncmp(T + p[mid], S, m) >= 0)
        hi = mid;
      else
        lo = mid + 1;
    }
    return strncmp(T + p[lo], S, m) != 0 ? -1 : lo;
  }
  int findUpperBound(char* S, int m) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (strncmp(T + p[mid], S, m) > 0)
        hi = mid;
      else
        lo = mid + 1;
    }
    if (strncmp(T + p[hi], S, m) != 0) hi--;
    assert(strncmp(T + p[hi], S, m) == 0);
    return hi;
  }
  int occurences(char* S, int m) {
    int L, R;
    if ((L = findLowerBound(S, m)) == -1) return 0;
    R = findUpperBound(S, m);
    return R - L + 1;
  }
  void printSA() {
    printf("Suffix Array of %s\n", T);
    for (int i = 0; i < n; ++i) printf("%d: %s\n", i, T + p[i]);
  }
} S, P[10];
int n;
int L[10], R[10];
int main() {
  while (scanf("%s", S.T) != EOF) {
    scanf("%d", &n);
    S.buildSA();
    for (int i = 0; i < n; ++i) {
      scanf("%s %d %d", P[i].T, L + i, R + i);
      P[i].buildSA();
    }
    int i, j, k, f, g, res = 0;
    set<string> used;
    for (i = 0; i < S.n - 1; ++i) {
      for (j = 1; j <= S.n - 1 - i; ++j) {
        f = 1;
        string s = "";
        for (k = 0; k < j; ++k) s.push_back(S.T[i + k]);
        if (used.find(s) != used.end()) continue;
        used.insert(s);
        for (k = 0; k < n && f == 1; ++k) {
          g = P[k].occurences(S.T + i, j);
          f &= (L[k] <= g && g <= R[k]);
        }
        res += f;
        if (f) {
        }
      }
    }
    printf("%d\n", res);
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const int MAXP = 2000 + 100;
int t[MAXP], c[MAXP], r[MAXP];
struct SuffixArray {
  char T[MAXP];
  int p[MAXP], n;
  void countSort(int k) {
    int m = max(255, n), i;
    for (i = 0; i <= m; ++i) c[i] = 0;
    for (i = 0; i < n; ++i) c[((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0)]++;
    for (i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--)
      t[--c[((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0)]] = p[i];
    for (i = 0; i < n; ++i) p[i] = t[i];
  }
  void buildSA() {
    n = strlen(T);
    T[n++] = '$';
    T[n] = '\0';
    for (int i = 0; i < n; ++i) {
      r[i] = T[i];
      p[i] = i;
    }
    int f, i;
    for (int k = 1; k < n; k *= 2) {
      countSort(k);
      countSort(0);
      f = t[p[0]] = 0;
      for (i = 1; i < n; ++i) {
        t[p[i]] = (((p[i] + (0)) < (n) ? (r[p[i] + (0)]) : 0) ==
                       ((p[i - 1] + (0)) < (n) ? (r[p[i - 1] + (0)]) : 0) &&
                   ((p[i] + (k)) < (n) ? (r[p[i] + (k)]) : 0) ==
                       ((p[i - 1] + (k)) < (n) ? (r[p[i - 1] + (k)]) : 0))
                      ? f
                      : ++f;
      }
      for (i = 0; i < n; ++i) r[i] = t[i];
      if (f == n - 1) break;
    }
  }
  int findLowerBound(char* S, int m) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (strncmp(T + p[mid], S, m) >= 0)
        hi = mid;
      else
        lo = mid + 1;
    }
    return strncmp(T + p[lo], S, m) != 0 ? -1 : lo;
  }
  int findUpperBound(char* S, int m) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (strncmp(T + p[mid], S, m) > 0)
        hi = mid;
      else
        lo = mid + 1;
    }
    if (strncmp(T + p[hi], S, m) != 0) hi--;
    assert(strncmp(T + p[hi], S, m) == 0);
    return hi;
  }
  int occurences(char* S, int m) {
    int L, R;
    if ((L = findLowerBound(S, m)) == -1) return 0;
    R = findUpperBound(S, m);
    return R - L + 1;
  }
  void printSA() {
    printf("Suffix Array of %s\n", T);
    for (int i = 0; i < n; ++i) printf("%d: %s\n", i, T + p[i]);
  }
} S, P[10];
int n;
int L[10], R[10];
int main() {
  while (scanf("%s", S.T) != EOF) {
    scanf("%d", &n);
    S.buildSA();
    for (int i = 0; i < n; ++i) {
      scanf("%s %d %d", P[i].T, L + i, R + i);
      P[i].buildSA();
    }
    int i, j, k, f, g, res = 0;
    set<string> used;
    for (i = 0; i < S.n - 1; ++i) {
      for (j = 1; j <= S.n - 1 - i; ++j) {
        f = 1;
        string s = "";
        for (k = 0; k < j; ++k) s.push_back(S.T[i + k]);
        if (used.find(s) != used.end()) continue;
        used.insert(s);
        for (k = 0; k < n && f == 1; ++k) {
          g = P[k].occurences(S.T + i, j);
          f &= (L[k] <= g && g <= R[k]);
        }
        res += f;
        if (f) {
        }
      }
    }
    printf("%d\n", res);
  }
  return 0;
}

```