#include <bits/stdc++.h>
using namespace std;
void read(long long int n = 10) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(n) << fixed;
}
long long int M = 1e9 + 7;
long long int M1 = 998244353;
long long int gen_base(const long long int before, const long long int after) {
  auto seed =
      std::chrono::high_resolution_clock::now().time_since_epoch().count();
  std::mt19937 mt_rand(seed);
  long long int base =
      std::uniform_int_distribution<long long int>(before + 1, after)(mt_rand);
  return base % 2 == 0 ? base - 1 : base;
}
long long int mod, base, mxPow;
vector<long long int> pow1(1, 1);
vector<unsigned long long int> pow2(1, 1);
struct Polyhash {
  vector<long long int> pref1, pref2;
  long long int n;
  Polyhash(string& s) {
    n = s.size();
    pref1.resize(n + 1);
    pref2.resize(n + 1);
    for (long long int i = 0; i < n; i++) {
      pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
      pref2[i + 1] = pref2[i] + s[i] * pow2[i];
    }
  }
  pair<long long int, unsigned long long int> findhash(long long int pos,
                                                       long long int len) {
    long long int hash1 = pref1[pos + len] - pref1[pos];
    unsigned long long int hash2 = pref2[pos + len] - pref2[pos];
    if (hash1 < 0) hash1 += mod;
    hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
    hash2 *= pow2[mxPow - (pos + len - 1)];
    return {hash1, hash2};
  }
};
void init_poly(long long int n) {
  mod = (long long int)1e9 + 123;
  mxPow = n;
  base = gen_base(256, mod);
  while ((long long int)pow1.size() <= n) {
    pow1.push_back((pow1.back() * base) % mod);
    pow2.push_back(pow2.back() * base);
  }
}
int32_t main() {
  read();
  init_poly(50001);
  string str;
  cin >> str;
  vector<string> subs;
  Polyhash* obj = new Polyhash(str);
  vector<pair<long long int, unsigned long long int>> poss;
  for (long long int j = 0; j < str.size(); j++) {
    for (long long int i = 1; j + i <= str.size(); i++) {
      poss.push_back(obj->findhash(j, i));
      subs.push_back(str.substr(j, i));
    }
  }
  long long int n;
  cin >> n;
  vector<map<pair<long long int, unsigned long long int>, long long int>> look(
      n);
  vector<pair<long long int, long long int>> bound(n);
  for (long long int i = 0; i < n; i++) {
    string arr;
    cin >> arr >> bound[i].first >> bound[i].second;
    Polyhash* temp = new Polyhash(arr);
    for (long long int j = 0; j < arr.size(); j++) {
      for (long long int ii = 1; j + ii <= arr.size(); ii++) {
        look[i][temp->findhash(j, ii)]++;
      }
    }
  }
  long long int coount = 0;
  set<pair<long long int, unsigned long long int>> done;
  for (long long int i = 0; i < poss.size(); i++) {
    if (done.find(poss[i]) == done.end()) {
      long long int ok = 1;
      for (long long int j = 0; j < n; j++) {
        long long int res = look[j][poss[i]];
        if (res < bound[j].first || res > bound[j].second) {
          ok = 0;
          break;
        }
      }
      if (ok) {
        coount++;
        done.insert(poss[i]);
      }
    }
  }
  cout << coount << "\n";
  ;
}

### 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;
void read(long long int n = 10) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(n) << fixed;
}
long long int M = 1e9 + 7;
long long int M1 = 998244353;
long long int gen_base(const long long int before, const long long int after) {
  auto seed =
      std::chrono::high_resolution_clock::now().time_since_epoch().count();
  std::mt19937 mt_rand(seed);
  long long int base =
      std::uniform_int_distribution<long long int>(before + 1, after)(mt_rand);
  return base % 2 == 0 ? base - 1 : base;
}
long long int mod, base, mxPow;
vector<long long int> pow1(1, 1);
vector<unsigned long long int> pow2(1, 1);
struct Polyhash {
  vector<long long int> pref1, pref2;
  long long int n;
  Polyhash(string& s) {
    n = s.size();
    pref1.resize(n + 1);
    pref2.resize(n + 1);
    for (long long int i = 0; i < n; i++) {
      pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
      pref2[i + 1] = pref2[i] + s[i] * pow2[i];
    }
  }
  pair<long long int, unsigned long long int> findhash(long long int pos,
                                                       long long int len) {
    long long int hash1 = pref1[pos + len] - pref1[pos];
    unsigned long long int hash2 = pref2[pos + len] - pref2[pos];
    if (hash1 < 0) hash1 += mod;
    hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
    hash2 *= pow2[mxPow - (pos + len - 1)];
    return {hash1, hash2};
  }
};
void init_poly(long long int n) {
  mod = (long long int)1e9 + 123;
  mxPow = n;
  base = gen_base(256, mod);
  while ((long long int)pow1.size() <= n) {
    pow1.push_back((pow1.back() * base) % mod);
    pow2.push_back(pow2.back() * base);
  }
}
int32_t main() {
  read();
  init_poly(50001);
  string str;
  cin >> str;
  vector<string> subs;
  Polyhash* obj = new Polyhash(str);
  vector<pair<long long int, unsigned long long int>> poss;
  for (long long int j = 0; j < str.size(); j++) {
    for (long long int i = 1; j + i <= str.size(); i++) {
      poss.push_back(obj->findhash(j, i));
      subs.push_back(str.substr(j, i));
    }
  }
  long long int n;
  cin >> n;
  vector<map<pair<long long int, unsigned long long int>, long long int>> look(
      n);
  vector<pair<long long int, long long int>> bound(n);
  for (long long int i = 0; i < n; i++) {
    string arr;
    cin >> arr >> bound[i].first >> bound[i].second;
    Polyhash* temp = new Polyhash(arr);
    for (long long int j = 0; j < arr.size(); j++) {
      for (long long int ii = 1; j + ii <= arr.size(); ii++) {
        look[i][temp->findhash(j, ii)]++;
      }
    }
  }
  long long int coount = 0;
  set<pair<long long int, unsigned long long int>> done;
  for (long long int i = 0; i < poss.size(); i++) {
    if (done.find(poss[i]) == done.end()) {
      long long int ok = 1;
      for (long long int j = 0; j < n; j++) {
        long long int res = look[j][poss[i]];
        if (res < bound[j].first || res > bound[j].second) {
          ok = 0;
          break;
        }
      }
      if (ok) {
        coount++;
        done.insert(poss[i]);
      }
    }
  }
  cout << coount << "\n";
  ;
}

```