#include <bits/stdc++.h>
const int MAX_N = (int)6e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;
using namespace std;
int n;
int whom[MAX_N];
vector<int> second;
int lll[20], rrr[20];
int sa[MAX_N], pos[MAX_N], for_time[MAX_N], len;
int lcp[MAX_N];
bool cmp(int x, int y) {
  if (len == 1) return pos[x] < pos[y];
  if (pos[x] != pos[y]) return pos[x] < pos[y];
  x = (x + len / 2) % int((second).size()),
  y = (y + len / 2) % int((second).size());
  return pos[x] < pos[y];
}
void outt(int x) {
  if (x < 0)
    cout << '#';
  else
    cout << char(x + 'a');
}
void out() {
  for (auto i : second) outt(i);
  cout << endl;
  for (int i = 0; i < int((second).size()); i++) {
    cout << i << " ->";
    for (int j = sa[i]; j < int((second).size()); j++) outt(second[j]);
    cout << ' ' << whom[sa[i]];
    cout << endl;
  }
}
void build_sa() {
  for (int i = 0; i < int((second).size()); i++) {
    pos[i] = second[i];
    sa[i] = i;
  }
  for (int h = 0;; h++) {
    len = (1 << h);
    sort(sa, sa + int((second).size()), &cmp);
    int color = 0;
    for (int i = 0; i < int((second).size()); i++) {
      if (i > 0 && cmp(sa[i - 1], sa[i])) color++;
      for_time[sa[i]] = color;
    }
    for (int i = 0; i < int((second).size()); i++) pos[i] = for_time[i];
    if (color == int((second).size()) - 1) break;
  }
  for (int i = 0, len = 0; i < int((second).size()); i++) {
    len = max(len - 1, 0);
    if (pos[i] == int((second).size()) - 1) {
      lcp[pos[i]] = len = 0;
      continue;
    }
    int j = sa[pos[i] + 1];
    while (second[(i + len) % int((second).size())] ==
           second[(j + len) % int((second).size())])
      len++;
    lcp[pos[i]] = len;
  }
}
int cnt[15][MAX_N];
int dp[20][MAX_N], lg[MAX_N];
void build_sparse() {
  for (int i = 0; i < int((second).size()); i++) {
    if (i > 0)
      for (int j = 1; j <= n; j++) cnt[j][i] = cnt[j][i - 1];
    if (whom[sa[i]] > 0) cnt[whom[sa[i]]][i]++;
  }
  for (int i = 0; i < int((second).size()); i++) dp[0][i] = lcp[i];
  for (int it = 1; it < 20; it++)
    for (int i = 0; i + (1 << it) - 1 < int((second).size()); i++)
      dp[it][i] = min(dp[it - 1][i], dp[it - 1][i + (1 << (it - 1))]);
  for (int i = 1, j = 0; i <= int((second).size()); i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
}
int get_min(int l, int r) {
  int len = r - l + 1;
  return min(dp[lg[len]][l], dp[lg[len]][r - (1 << lg[len]) + 1]);
}
int getL(int x, int len) {
  int l = 0, r = x - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get_min(mid, x - 1) >= len) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
int getR(int x, int len) {
  int l = x + 1, r = int((second).size()) - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get_min(x, mid - 1) >= len) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int how_many(int L, int R, int tp) {
  int res = cnt[tp][R];
  if (L > 0) res -= cnt[tp][L - 1];
  return res;
}
int FindL(int id, int L, int R, int tp) {
  int l = L, r = R, mid = -1, ans = -1, now;
  while (l <= r) {
    mid = (l + r) / 2;
    now = how_many(getL(id, mid), getR(id, mid), tp);
    if (lll[tp] <= now) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int FindR(int id, int L, int R, int tp) {
  int l = L, r = R, mid = -1, ans = -1, now;
  while (l <= r) {
    mid = (l + r) / 2;
    now = how_many(getL(id, mid), getR(id, mid), tp);
    if (now <= rrr[tp]) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
int tt;
int ccount(int id, int L, int R) {
  pair<int, int> now = make_pair(L, R);
  for (int i = 1; i <= n; i++) {
    int l = FindL(id, L, R, i), r = FindR(id, L, R, i);
    swap(l, r);
    if (l == -1 || r == -1 || l > r) return 0;
    if (now.first == -1)
      now = make_pair(l, r);
    else {
      if (now.second < l || r < now.first) return 0;
      now.first = max(now.first, l);
      now.second = min(now.second, r);
    }
  }
  return now.second - now.first + 1;
}
long long get() {
  long long res = 0;
  for (int i = 0, last = -1; i < int((second).size()); i++) {
    if (whom[sa[i]] != 0) continue;
    int len = 0;
    if (last >= 0) {
      len = get_min(last, i - 1);
    }
    if (len + 1 <= tt - sa[i]) res += ccount(i, len + 1, tt - sa[i]);
    last = i;
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(NULL), cin.tie(NULL);
  string nw;
  cin >> nw;
  tt = int((nw).size());
  for (int j = int((second).size());
       j <= int((second).size()) + int((nw).size()) - 1; j++)
    whom[j] = 0;
  whom[int((second).size()) + int((nw).size())] = -1;
  for (auto i : nw) second.push_back(i - 'a');
  int hey = 0;
  second.push_back(--hey);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> nw >> lll[i] >> rrr[i];
    for (int j = int((second).size());
         j <= int((second).size()) + int((nw).size()) - 1; j++)
      whom[j] = i;
    whom[int((second).size()) + int((nw).size())] = -1;
    for (auto i : nw) second.push_back(i - 'a');
    second.push_back(--hey);
  }
  build_sa();
  build_sparse();
  cout << get();
  return 0;
}

### Prompt

Your challenge is to write 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>
const int MAX_N = (int)6e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;
using namespace std;
int n;
int whom[MAX_N];
vector<int> second;
int lll[20], rrr[20];
int sa[MAX_N], pos[MAX_N], for_time[MAX_N], len;
int lcp[MAX_N];
bool cmp(int x, int y) {
  if (len == 1) return pos[x] < pos[y];
  if (pos[x] != pos[y]) return pos[x] < pos[y];
  x = (x + len / 2) % int((second).size()),
  y = (y + len / 2) % int((second).size());
  return pos[x] < pos[y];
}
void outt(int x) {
  if (x < 0)
    cout << '#';
  else
    cout << char(x + 'a');
}
void out() {
  for (auto i : second) outt(i);
  cout << endl;
  for (int i = 0; i < int((second).size()); i++) {
    cout << i << " ->";
    for (int j = sa[i]; j < int((second).size()); j++) outt(second[j]);
    cout << ' ' << whom[sa[i]];
    cout << endl;
  }
}
void build_sa() {
  for (int i = 0; i < int((second).size()); i++) {
    pos[i] = second[i];
    sa[i] = i;
  }
  for (int h = 0;; h++) {
    len = (1 << h);
    sort(sa, sa + int((second).size()), &cmp);
    int color = 0;
    for (int i = 0; i < int((second).size()); i++) {
      if (i > 0 && cmp(sa[i - 1], sa[i])) color++;
      for_time[sa[i]] = color;
    }
    for (int i = 0; i < int((second).size()); i++) pos[i] = for_time[i];
    if (color == int((second).size()) - 1) break;
  }
  for (int i = 0, len = 0; i < int((second).size()); i++) {
    len = max(len - 1, 0);
    if (pos[i] == int((second).size()) - 1) {
      lcp[pos[i]] = len = 0;
      continue;
    }
    int j = sa[pos[i] + 1];
    while (second[(i + len) % int((second).size())] ==
           second[(j + len) % int((second).size())])
      len++;
    lcp[pos[i]] = len;
  }
}
int cnt[15][MAX_N];
int dp[20][MAX_N], lg[MAX_N];
void build_sparse() {
  for (int i = 0; i < int((second).size()); i++) {
    if (i > 0)
      for (int j = 1; j <= n; j++) cnt[j][i] = cnt[j][i - 1];
    if (whom[sa[i]] > 0) cnt[whom[sa[i]]][i]++;
  }
  for (int i = 0; i < int((second).size()); i++) dp[0][i] = lcp[i];
  for (int it = 1; it < 20; it++)
    for (int i = 0; i + (1 << it) - 1 < int((second).size()); i++)
      dp[it][i] = min(dp[it - 1][i], dp[it - 1][i + (1 << (it - 1))]);
  for (int i = 1, j = 0; i <= int((second).size()); i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
}
int get_min(int l, int r) {
  int len = r - l + 1;
  return min(dp[lg[len]][l], dp[lg[len]][r - (1 << lg[len]) + 1]);
}
int getL(int x, int len) {
  int l = 0, r = x - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get_min(mid, x - 1) >= len) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
int getR(int x, int len) {
  int l = x + 1, r = int((second).size()) - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get_min(x, mid - 1) >= len) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int how_many(int L, int R, int tp) {
  int res = cnt[tp][R];
  if (L > 0) res -= cnt[tp][L - 1];
  return res;
}
int FindL(int id, int L, int R, int tp) {
  int l = L, r = R, mid = -1, ans = -1, now;
  while (l <= r) {
    mid = (l + r) / 2;
    now = how_many(getL(id, mid), getR(id, mid), tp);
    if (lll[tp] <= now) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int FindR(int id, int L, int R, int tp) {
  int l = L, r = R, mid = -1, ans = -1, now;
  while (l <= r) {
    mid = (l + r) / 2;
    now = how_many(getL(id, mid), getR(id, mid), tp);
    if (now <= rrr[tp]) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
int tt;
int ccount(int id, int L, int R) {
  pair<int, int> now = make_pair(L, R);
  for (int i = 1; i <= n; i++) {
    int l = FindL(id, L, R, i), r = FindR(id, L, R, i);
    swap(l, r);
    if (l == -1 || r == -1 || l > r) return 0;
    if (now.first == -1)
      now = make_pair(l, r);
    else {
      if (now.second < l || r < now.first) return 0;
      now.first = max(now.first, l);
      now.second = min(now.second, r);
    }
  }
  return now.second - now.first + 1;
}
long long get() {
  long long res = 0;
  for (int i = 0, last = -1; i < int((second).size()); i++) {
    if (whom[sa[i]] != 0) continue;
    int len = 0;
    if (last >= 0) {
      len = get_min(last, i - 1);
    }
    if (len + 1 <= tt - sa[i]) res += ccount(i, len + 1, tt - sa[i]);
    last = i;
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(NULL), cin.tie(NULL);
  string nw;
  cin >> nw;
  tt = int((nw).size());
  for (int j = int((second).size());
       j <= int((second).size()) + int((nw).size()) - 1; j++)
    whom[j] = 0;
  whom[int((second).size()) + int((nw).size())] = -1;
  for (auto i : nw) second.push_back(i - 'a');
  int hey = 0;
  second.push_back(--hey);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> nw >> lll[i] >> rrr[i];
    for (int j = int((second).size());
         j <= int((second).size()) + int((nw).size()) - 1; j++)
      whom[j] = i;
    whom[int((second).size()) + int((nw).size())] = -1;
    for (auto i : nw) second.push_back(i - 'a');
    second.push_back(--hey);
  }
  build_sa();
  build_sparse();
  cout << get();
  return 0;
}

```