#include <bits/stdc++.h>
using namespace std;
bool debug = false;
int n, m, k;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long ln, lk, lm;
int dp[50105][15];
class Sam {
 public:
  static const int MAXLEN = 50105;
  struct state {
    int len, link;
    map<int, int> next;
  };
  state st[MAXLEN * 2];
  int sz, last;
  Sam() {
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
  }
  void sa_extend(int c, int id) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    if (id != -1) dp[cur][id]++;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
      st[p].next[c] = cur;
    if (p == -1)
      st[cur].link = 0;
    else {
      int q = st[p].next[c];
      if (st[p].len + 1 == st[q].len)
        st[cur].link = q;
      else {
        int clone = sz++;
        st[clone].len = st[p].len + 1;
        st[clone].next = st[q].next;
        st[clone].link = st[q].link;
        for (; p != -1 && st[p].next[c] == q; p = st[p].link)
          st[p].next[c] = clone;
        st[q].link = st[cur].link = clone;
      }
    }
    last = cur;
  }
} sa;
char s[50105];
vector<int> child[50105];
int l[20], r[20], minlen[50105];
long long ans;
void dfs(int x, int pa) {
  for (int c : child[x])
    if (c) {
      dfs(c, x);
    }
  for (int i = 0; i <= n; i++)
    if (pa != -1) {
      dp[pa][i] += dp[x][i];
    }
  if (x == 0) return;
  if (!dp[x][0]) return;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    if (dp[x][i] < l[i] || dp[x][i] > r[i]) return;
  }
  ans += sa.st[x].len - minlen[x] + 1;
}
int main() {
  scanf("%s", s);
  for (int i = 0; s[i]; i++) {
    sa.sa_extend(s[i] - 'a', 0);
  }
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    sa.sa_extend(-1, -1);
    scanf("%s%d%d", s, l + i, r + i);
    for (int j = 0; s[j]; j++) {
      sa.sa_extend(s[j] - 'a', i);
    }
  }
  for (int(i) = 0; (i) < (int)(sa.sz); (i)++)
    if (sa.st[i].link != -1) {
      child[sa.st[i].link].push_back(i);
      minlen[i] = sa.st[sa.st[i].link].len + 1;
    }
  dfs(0, -1);
  printf("%lld\n", ans);
  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>
using namespace std;
bool debug = false;
int n, m, k;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long ln, lk, lm;
int dp[50105][15];
class Sam {
 public:
  static const int MAXLEN = 50105;
  struct state {
    int len, link;
    map<int, int> next;
  };
  state st[MAXLEN * 2];
  int sz, last;
  Sam() {
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
  }
  void sa_extend(int c, int id) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    if (id != -1) dp[cur][id]++;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
      st[p].next[c] = cur;
    if (p == -1)
      st[cur].link = 0;
    else {
      int q = st[p].next[c];
      if (st[p].len + 1 == st[q].len)
        st[cur].link = q;
      else {
        int clone = sz++;
        st[clone].len = st[p].len + 1;
        st[clone].next = st[q].next;
        st[clone].link = st[q].link;
        for (; p != -1 && st[p].next[c] == q; p = st[p].link)
          st[p].next[c] = clone;
        st[q].link = st[cur].link = clone;
      }
    }
    last = cur;
  }
} sa;
char s[50105];
vector<int> child[50105];
int l[20], r[20], minlen[50105];
long long ans;
void dfs(int x, int pa) {
  for (int c : child[x])
    if (c) {
      dfs(c, x);
    }
  for (int i = 0; i <= n; i++)
    if (pa != -1) {
      dp[pa][i] += dp[x][i];
    }
  if (x == 0) return;
  if (!dp[x][0]) return;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    if (dp[x][i] < l[i] || dp[x][i] > r[i]) return;
  }
  ans += sa.st[x].len - minlen[x] + 1;
}
int main() {
  scanf("%s", s);
  for (int i = 0; s[i]; i++) {
    sa.sa_extend(s[i] - 'a', 0);
  }
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    sa.sa_extend(-1, -1);
    scanf("%s%d%d", s, l + i, r + i);
    for (int j = 0; s[j]; j++) {
      sa.sa_extend(s[j] - 'a', i);
    }
  }
  for (int(i) = 0; (i) < (int)(sa.sz); (i)++)
    if (sa.st[i].link != -1) {
      child[sa.st[i].link].push_back(i);
      minlen[i] = sa.st[sa.st[i].link].len + 1;
    }
  dfs(0, -1);
  printf("%lld\n", ans);
  return 0;
}

```