#include <bits/stdc++.h>
using namespace std;
const int MAXL = 2002;
const int MAXN = 12;
char s[MAXL + 1];
char ps[MAXN][MAXL + 1];
int pls[MAXN];
int lcs[MAXN], rcs[MAXN];
int lcps[MAXN][MAXL + 1][MAXL + 1];
int slcp[MAXL + 1][MAXL + 1];
bool sufcmp(int a, int b) {
  int off = slcp[a][b];
  a += off;
  b += off;
  return s[a] < s[b];
}
int ptrs[MAXN][MAXL + 1];
int main() {
  int n;
  while (scanf("%s%d", s, &n) >= 1) {
    int l = strlen(s);
    for (int i = 0; i < n; i++) {
      scanf("%s%d%d", ps[i], &lcs[i], &rcs[i]);
      pls[i] = strlen(ps[i]);
      int m = pls[i];
      for (int a = 0; a <= l; a++) lcps[i][a][m] = 0;
      for (int b = 0; b <= m; b++) lcps[i][l][b] = 0;
      for (int a = l - 1; a >= 0; a--)
        for (int b = m - 1; b >= 0; b--) {
          if (s[a] == ps[i][b])
            lcps[i][a][b] = lcps[i][a + 1][b + 1] + 1;
          else
            lcps[i][a][b] = 0;
        }
      for (int a = 0; a <= l; a++) sort(lcps[i][a], lcps[i][a] + m + 1);
    }
    memset(slcp, 0, sizeof slcp);
    for (int a = l - 1; a >= 0; a--)
      for (int b = l - 1; b >= 0; b--)
        if (s[a] == s[b]) slcp[a][b] = slcp[a + 1][b + 1] + 1;
    memset(ptrs, 0, sizeof ptrs);
    int ans = 0;
    for (int len = 1; len <= l; len++) {
      static vector<int> all;
      all.clear();
      for (int st = 0; st + len <= l; st++) {
        bool g = true;
        for (int i = 0; i < n; i++) {
          int m = pls[i];
          while (ptrs[i][st] <= m && lcps[i][st][ptrs[i][st]] < len)
            ptrs[i][st]++;
          int mycnt = m + 1 - ptrs[i][st];
          g = g && lcs[i] <= mycnt && mycnt <= rcs[i];
        }
        if (g) all.push_back(st);
      }
      sort(all.begin(), all.end(), sufcmp);
      for (int i = 0; i < ((int)(all).size()); i++)
        if (i == 0 || slcp[all[i - 1]][all[i]] < len) ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 MAXL = 2002;
const int MAXN = 12;
char s[MAXL + 1];
char ps[MAXN][MAXL + 1];
int pls[MAXN];
int lcs[MAXN], rcs[MAXN];
int lcps[MAXN][MAXL + 1][MAXL + 1];
int slcp[MAXL + 1][MAXL + 1];
bool sufcmp(int a, int b) {
  int off = slcp[a][b];
  a += off;
  b += off;
  return s[a] < s[b];
}
int ptrs[MAXN][MAXL + 1];
int main() {
  int n;
  while (scanf("%s%d", s, &n) >= 1) {
    int l = strlen(s);
    for (int i = 0; i < n; i++) {
      scanf("%s%d%d", ps[i], &lcs[i], &rcs[i]);
      pls[i] = strlen(ps[i]);
      int m = pls[i];
      for (int a = 0; a <= l; a++) lcps[i][a][m] = 0;
      for (int b = 0; b <= m; b++) lcps[i][l][b] = 0;
      for (int a = l - 1; a >= 0; a--)
        for (int b = m - 1; b >= 0; b--) {
          if (s[a] == ps[i][b])
            lcps[i][a][b] = lcps[i][a + 1][b + 1] + 1;
          else
            lcps[i][a][b] = 0;
        }
      for (int a = 0; a <= l; a++) sort(lcps[i][a], lcps[i][a] + m + 1);
    }
    memset(slcp, 0, sizeof slcp);
    for (int a = l - 1; a >= 0; a--)
      for (int b = l - 1; b >= 0; b--)
        if (s[a] == s[b]) slcp[a][b] = slcp[a + 1][b + 1] + 1;
    memset(ptrs, 0, sizeof ptrs);
    int ans = 0;
    for (int len = 1; len <= l; len++) {
      static vector<int> all;
      all.clear();
      for (int st = 0; st + len <= l; st++) {
        bool g = true;
        for (int i = 0; i < n; i++) {
          int m = pls[i];
          while (ptrs[i][st] <= m && lcps[i][st][ptrs[i][st]] < len)
            ptrs[i][st]++;
          int mycnt = m + 1 - ptrs[i][st];
          g = g && lcs[i] <= mycnt && mycnt <= rcs[i];
        }
        if (g) all.push_back(st);
      }
      sort(all.begin(), all.end(), sufcmp);
      for (int i = 0; i < ((int)(all).size()); i++)
        if (i == 0 || slcp[all[i - 1]][all[i]] < len) ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}

```