#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9 + 123, MAX_N = (int)6e5 + 5;
vector<char> second;
int sa[MAX_N], _sa[MAX_N];
int pos[MAX_N], col[MAX_N], id[MAX_N], w[MAX_N];
int lcp[MAX_N];
inline void build() {
  int cnt = 0;
  for (int i = 0; i < (int)((second).size()); i++) {
    pos[i] = second[i];
    cnt = max(cnt, (int)second[i]);
    sa[i] = i;
  }
  for (int len = 1, prev;; len *= 2) {
    prev = len / 2;
    if (prev >= (int)((second).size())) break;
    for (int i = 0; i < (int)((second).size()); i++) {
      _sa[i] = sa[i] - prev;
      if (_sa[i] < 0) _sa[i] += (int)((second).size());
    }
    memset(col, 0, sizeof col);
    for (int i = 0; i < (int)((second).size()); i++) col[pos[_sa[i]]]++;
    for (int i = 1; i <= cnt; i++) col[i] += col[i - 1];
    for (int i = (int)((second).size()) - 1; i >= 0; i--)
      sa[--col[pos[_sa[i]]]] = _sa[i];
    col[0] = 0;
    for (int i = 1; i < (int)((second).size()); i++) {
      col[i] = col[i - 1];
      if (pos[sa[i]] != pos[sa[i - 1]] ||
          pos[(sa[i] + prev) % (int)((second).size())] !=
              pos[(sa[i - 1] + prev) % (int)((second).size())])
        col[i]++;
      cnt = col[i];
    }
    for (int i = 0; i < (int)((second).size()); i++) pos[sa[i]] = col[i];
    if (col[(int)((second).size()) - 1] == (int)((second).size()) - 1) break;
  }
  for (int i = 0, len = 0; i < (int)((second).size()); i++) {
    if (pos[i] == (int)((second).size()) - 1) {
      len = 0;
      continue;
    }
    len = max(0, len - 1);
    int j = sa[pos[i] + 1];
    while (i + len < (int)((second).size()) &&
           j + len < (int)((second).size()) &&
           second[i + len] == second[j + len])
      len++;
    lcp[pos[i]] = len;
  }
  for (int i = 0; i < (int)((second).size()); i++) w[pos[i]] = id[i];
}
int d[20][MAX_N], lg[MAX_N];
inline void Sparse() {
  for (int i = 0; i < (int)((second).size()); i++) d[0][i] = lcp[i];
  for (int it = 1; it < 20; it++) {
    for (int i = 0; i < (int)((second).size()); i++) {
      d[it][i] = d[it - 1][i];
      if (i + (1 << (it - 1)) < (int)((second).size()))
        d[it][i] = min(d[it][i], d[it - 1][i + (1 << (it - 1))]);
    }
  }
  for (int i = 1, j = 0; i <= (int)6e5; i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
}
inline int get(int l, int r) {
  int len = r - l + 1;
  return min(d[lg[len]][l], d[lg[len]][r - (1 << lg[len]) + 1]);
}
inline int getLcp(int l, int r) {
  r--;
  return get(l, r);
}
inline int getL(int x, int val) {
  int l = 0, r = x - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get(mid, x - 1) >= val) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
inline int getR(int x, int val) {
  int l = x + 1, r = (int)((second).size()) - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get(x, mid - 1) >= val) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int sz;
struct tree {
  int l, r, sum;
  tree() {}
  tree(int l, int r, int sum) : l(l), r(r), sum(sum) {}
} t[MAX_N * 20];
int Build(int tl = 0, int tr = (int)((second).size()) - 1) {
  if (tl == tr) {
    t[++sz] = tree(-1, -1, 0);
    return sz;
  }
  int tm = (tl + tr) / 2;
  int now = ++sz;
  t[now] = tree(Build(tl, tm), Build(tm + 1, tr), 0);
  return now;
}
int update(int v, int x, int y, int tl = 0,
           int tr = (int)((second).size()) - 1) {
  int now = ++sz;
  t[now] = t[v];
  if (tl == tr) {
    t[now].sum += y;
    return now;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm)
    t[now].l = update(t[v].l, x, y, tl, tm);
  else
    t[now].r = update(t[v].r, x, y, tm + 1, tr);
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum;
  return now;
}
int Get(int v, int x, int tl = 0, int tr = (int)((second).size()) - 1) {
  if (tl == tr) return t[v].sum;
  int tm = (tl + tr) / 2;
  if (x <= tm) return Get(t[v].l, x, tl, tm);
  return Get(t[v].r, x, tm + 1, tr);
}
int root[MAX_N];
void Tree() {
  root[0] = Build();
  for (int i = 0, last = root[0]; i < (int)((second).size()); i++) {
    root[i] = update(last, w[i], 1);
    last = root[i];
  }
}
int Count(int l, int r, int k) {
  int res = Get(root[r], k);
  if (l > 0) res -= Get(root[l - 1], k);
  return res;
}
int n;
string a;
pair<int, int> seg[12];
long long ans;
int len, what[MAX_N];
pair<int, int> Find(int x) {
  int now = len - what[sa[x]];
  pair<int, int> res = make_pair(1, now);
  for (int i = 1; i <= n; i++) {
    int l = 1, r = now, mid = -1, L = now + 1, R = 0;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Count(getL(x, mid), getR(x, mid), i) <= seg[i].second) {
        L = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    l = 1, r = now, mid = -1;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Count(getL(x, mid), getR(x, mid), i) >= seg[i].first) {
        R = mid;
        l = mid + 1;
      } else
        r = mid - 1;
    }
    if (L > R || res.first > R || L > res.second) return make_pair(0, 0);
    res.first = max(res.first, L);
    res.second = min(res.second, R);
  }
  return res;
}
void Answer() {
  for (int i = 0, last = -1; i < (int)((second).size()); i++) {
    if (w[i] == 0) {
      pair<int, int> now = Find(i);
      if (last != -1) now.first = max(now.first, getLcp(last, i) + 1);
      if (now.first <= now.second && now.first > 0)
        ans += now.second - now.first + 1;
      last = i;
    }
  }
}
int main() {
  ios_base ::sync_with_stdio(NULL), cin.tie(NULL);
  cin >> a >> n;
  len = (int)((a).size());
  int num = 0;
  int last = 96;
  for (auto i : a) {
    id[(int)((second).size())] = 0;
    what[num++] = (int)((second).size());
    second.push_back(i);
  }
  id[(int)((second).size())] = -1;
  second.push_back(char(last--));
  for (int i = 1; i <= n; i++) {
    cin >> a >> seg[i].first >> seg[i].second;
    for (auto j : a) {
      id[(int)((second).size())] = i;
      second.push_back(j);
    }
    id[(int)((second).size())] = -1;
    second.push_back(char(last--));
  }
  build();
  Sparse();
  Tree();
  Answer();
  cout << ans;
  return 0;
}

### Prompt

Please formulate 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;
const int inf = (int)1e9 + 123, MAX_N = (int)6e5 + 5;
vector<char> second;
int sa[MAX_N], _sa[MAX_N];
int pos[MAX_N], col[MAX_N], id[MAX_N], w[MAX_N];
int lcp[MAX_N];
inline void build() {
  int cnt = 0;
  for (int i = 0; i < (int)((second).size()); i++) {
    pos[i] = second[i];
    cnt = max(cnt, (int)second[i]);
    sa[i] = i;
  }
  for (int len = 1, prev;; len *= 2) {
    prev = len / 2;
    if (prev >= (int)((second).size())) break;
    for (int i = 0; i < (int)((second).size()); i++) {
      _sa[i] = sa[i] - prev;
      if (_sa[i] < 0) _sa[i] += (int)((second).size());
    }
    memset(col, 0, sizeof col);
    for (int i = 0; i < (int)((second).size()); i++) col[pos[_sa[i]]]++;
    for (int i = 1; i <= cnt; i++) col[i] += col[i - 1];
    for (int i = (int)((second).size()) - 1; i >= 0; i--)
      sa[--col[pos[_sa[i]]]] = _sa[i];
    col[0] = 0;
    for (int i = 1; i < (int)((second).size()); i++) {
      col[i] = col[i - 1];
      if (pos[sa[i]] != pos[sa[i - 1]] ||
          pos[(sa[i] + prev) % (int)((second).size())] !=
              pos[(sa[i - 1] + prev) % (int)((second).size())])
        col[i]++;
      cnt = col[i];
    }
    for (int i = 0; i < (int)((second).size()); i++) pos[sa[i]] = col[i];
    if (col[(int)((second).size()) - 1] == (int)((second).size()) - 1) break;
  }
  for (int i = 0, len = 0; i < (int)((second).size()); i++) {
    if (pos[i] == (int)((second).size()) - 1) {
      len = 0;
      continue;
    }
    len = max(0, len - 1);
    int j = sa[pos[i] + 1];
    while (i + len < (int)((second).size()) &&
           j + len < (int)((second).size()) &&
           second[i + len] == second[j + len])
      len++;
    lcp[pos[i]] = len;
  }
  for (int i = 0; i < (int)((second).size()); i++) w[pos[i]] = id[i];
}
int d[20][MAX_N], lg[MAX_N];
inline void Sparse() {
  for (int i = 0; i < (int)((second).size()); i++) d[0][i] = lcp[i];
  for (int it = 1; it < 20; it++) {
    for (int i = 0; i < (int)((second).size()); i++) {
      d[it][i] = d[it - 1][i];
      if (i + (1 << (it - 1)) < (int)((second).size()))
        d[it][i] = min(d[it][i], d[it - 1][i + (1 << (it - 1))]);
    }
  }
  for (int i = 1, j = 0; i <= (int)6e5; i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
}
inline int get(int l, int r) {
  int len = r - l + 1;
  return min(d[lg[len]][l], d[lg[len]][r - (1 << lg[len]) + 1]);
}
inline int getLcp(int l, int r) {
  r--;
  return get(l, r);
}
inline int getL(int x, int val) {
  int l = 0, r = x - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get(mid, x - 1) >= val) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ans;
}
inline int getR(int x, int val) {
  int l = x + 1, r = (int)((second).size()) - 1, ans = x, mid = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (get(x, mid - 1) >= val) {
      ans = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ans;
}
int sz;
struct tree {
  int l, r, sum;
  tree() {}
  tree(int l, int r, int sum) : l(l), r(r), sum(sum) {}
} t[MAX_N * 20];
int Build(int tl = 0, int tr = (int)((second).size()) - 1) {
  if (tl == tr) {
    t[++sz] = tree(-1, -1, 0);
    return sz;
  }
  int tm = (tl + tr) / 2;
  int now = ++sz;
  t[now] = tree(Build(tl, tm), Build(tm + 1, tr), 0);
  return now;
}
int update(int v, int x, int y, int tl = 0,
           int tr = (int)((second).size()) - 1) {
  int now = ++sz;
  t[now] = t[v];
  if (tl == tr) {
    t[now].sum += y;
    return now;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm)
    t[now].l = update(t[v].l, x, y, tl, tm);
  else
    t[now].r = update(t[v].r, x, y, tm + 1, tr);
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum;
  return now;
}
int Get(int v, int x, int tl = 0, int tr = (int)((second).size()) - 1) {
  if (tl == tr) return t[v].sum;
  int tm = (tl + tr) / 2;
  if (x <= tm) return Get(t[v].l, x, tl, tm);
  return Get(t[v].r, x, tm + 1, tr);
}
int root[MAX_N];
void Tree() {
  root[0] = Build();
  for (int i = 0, last = root[0]; i < (int)((second).size()); i++) {
    root[i] = update(last, w[i], 1);
    last = root[i];
  }
}
int Count(int l, int r, int k) {
  int res = Get(root[r], k);
  if (l > 0) res -= Get(root[l - 1], k);
  return res;
}
int n;
string a;
pair<int, int> seg[12];
long long ans;
int len, what[MAX_N];
pair<int, int> Find(int x) {
  int now = len - what[sa[x]];
  pair<int, int> res = make_pair(1, now);
  for (int i = 1; i <= n; i++) {
    int l = 1, r = now, mid = -1, L = now + 1, R = 0;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Count(getL(x, mid), getR(x, mid), i) <= seg[i].second) {
        L = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    l = 1, r = now, mid = -1;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Count(getL(x, mid), getR(x, mid), i) >= seg[i].first) {
        R = mid;
        l = mid + 1;
      } else
        r = mid - 1;
    }
    if (L > R || res.first > R || L > res.second) return make_pair(0, 0);
    res.first = max(res.first, L);
    res.second = min(res.second, R);
  }
  return res;
}
void Answer() {
  for (int i = 0, last = -1; i < (int)((second).size()); i++) {
    if (w[i] == 0) {
      pair<int, int> now = Find(i);
      if (last != -1) now.first = max(now.first, getLcp(last, i) + 1);
      if (now.first <= now.second && now.first > 0)
        ans += now.second - now.first + 1;
      last = i;
    }
  }
}
int main() {
  ios_base ::sync_with_stdio(NULL), cin.tie(NULL);
  cin >> a >> n;
  len = (int)((a).size());
  int num = 0;
  int last = 96;
  for (auto i : a) {
    id[(int)((second).size())] = 0;
    what[num++] = (int)((second).size());
    second.push_back(i);
  }
  id[(int)((second).size())] = -1;
  second.push_back(char(last--));
  for (int i = 1; i <= n; i++) {
    cin >> a >> seg[i].first >> seg[i].second;
    for (auto j : a) {
      id[(int)((second).size())] = i;
      second.push_back(j);
    }
    id[(int)((second).size())] = -1;
    second.push_back(char(last--));
  }
  build();
  Sparse();
  Tree();
  Answer();
  cout << ans;
  return 0;
}

```