#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
const int INF = 100000007;
char s[N], s1[N];
struct coor {
  int l, r;
} a[N];
int n, m, i, j, k, l, r, p, key, len;
int q[N * 2], cnt[N * 2], num[N * 2];
struct Suffix_Automation {
  int tot, tail;
  struct Suffix_Node {
    int son[26], len, fa;
    coor c;
    priority_queue<int> q;
  } a[N * 2], empty;
  void clear() {
    for (int i = 0; i <= tot; i++) a[i] = empty;
    tot = tail = 0;
  }
  void add(int c) {
    int np = ++tot;
    a[np].len = a[tail].len + 1;
    int p = tail;
    tail = np;
    for (; p && !a[p].son[c]; p = a[p].fa) a[p].son[c] = np;
    if (!a[p].son[c])
      a[p].son[c] = np;
    else {
      int q = a[p].son[c];
      if (a[q].len == a[p].len + 1)
        a[np].fa = q;
      else {
        int nq = ++tot;
        for (int i = 0; i < 26; i++) a[nq].son[i] = a[q].son[i];
        a[nq].fa = a[q].fa;
        a[nq].len = a[p].len + 1;
        a[q].fa = a[np].fa = nq;
        for (; a[p].son[c] == q; p = a[p].fa) a[p].son[c] = nq;
      }
    }
  }
  void insert(char *s) {
    int i, n = strlen(s);
    for (i = 0; i < n; i++) add(s[i] - 'a');
    for (i = 1; i <= tot; i++)
      a[i].c.r = a[i].len, a[i].c.l = a[a[i].fa].len + 1;
  }
  int solve(int low, int high) {
    int p, l = 1, r = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= tot; i++) cnt[a[i].fa]++;
    for (int i = 1; i <= tot; i++)
      if (!cnt[i]) q[++r] = i;
    while (l <= r) {
      p = q[l++];
      if (p) {
        if (num[p] + a[p].q.size() < low) a[p].c.r = a[p].c.l - 1;
        if (num[p] > high) a[p].c.l = a[p].c.r + 1;
        while (num[p] < low - 1 && a[p].q.size()) num[p]++, a[p].q.pop();
        if (num[p] == low - 1 && a[p].q.size())
          a[p].c.r = min(a[p].c.r, a[p].q.top());
        while (num[p] < high && a[p].q.size()) num[p]++, a[p].q.pop();
        if (num[p] == high && a[p].q.size())
          a[p].c.l = max(a[p].c.r, a[p].q.top() + 1);
        while (a[p].q.size()) num[p]++, a[p].q.pop();
        num[a[p].fa] += num[p];
        if (!--cnt[a[p].fa]) q[++r] = a[p].fa;
      }
      while (a[p].q.size()) a[p].q.pop();
    }
  }
  int calc() {
    int i, ans = 0;
    for (i = 0; i <= tot; i++) ans += max(0, a[i].c.r - a[i].c.l + 1);
    return ans;
  }
  void draw() {
    for (int i = 0; i <= tot; i++) {
      printf("node:%d len=%d fa=%d size:(%d,%d) son:", i, a[i].len, a[i].fa,
             a[i].c.l, a[i].c.r);
      for (int j = 0; j < 26; j++)
        if (a[i].son[j]) printf("(%d,%d)", j, a[i].son[j]);
      cout << endl;
    }
    cout << endl;
  }
} SAM;
int main() {
  scanf("%s", s);
  n = strlen(s);
  SAM.insert(s);
  scanf("%d", &m);
  while (m--) {
    scanf("%s%d%d", s1, &l, &r);
    len = strlen(s1);
    for (i = j = k = 0; i < len; i++) {
      key = s1[i] - 'a';
      if (SAM.a[k].son[key])
        j++, k = SAM.a[k].son[key], SAM.a[k].q.push(j);
      else {
        while (k && !SAM.a[k].son[key]) k = SAM.a[k].fa;
        if (SAM.a[k].son[key]) {
          j = SAM.a[k].len + 1;
          k = SAM.a[k].son[key];
          SAM.a[k].q.push(j);
        } else
          j = k = 0;
      }
    }
    SAM.solve(l, r);
    memset(s1, 0, sizeof(s1));
  }
  printf("%d\n", SAM.calc() - 1);
  return 0;
}

### Prompt

Create a solution in CPP for 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 N = 50010;
const int INF = 100000007;
char s[N], s1[N];
struct coor {
  int l, r;
} a[N];
int n, m, i, j, k, l, r, p, key, len;
int q[N * 2], cnt[N * 2], num[N * 2];
struct Suffix_Automation {
  int tot, tail;
  struct Suffix_Node {
    int son[26], len, fa;
    coor c;
    priority_queue<int> q;
  } a[N * 2], empty;
  void clear() {
    for (int i = 0; i <= tot; i++) a[i] = empty;
    tot = tail = 0;
  }
  void add(int c) {
    int np = ++tot;
    a[np].len = a[tail].len + 1;
    int p = tail;
    tail = np;
    for (; p && !a[p].son[c]; p = a[p].fa) a[p].son[c] = np;
    if (!a[p].son[c])
      a[p].son[c] = np;
    else {
      int q = a[p].son[c];
      if (a[q].len == a[p].len + 1)
        a[np].fa = q;
      else {
        int nq = ++tot;
        for (int i = 0; i < 26; i++) a[nq].son[i] = a[q].son[i];
        a[nq].fa = a[q].fa;
        a[nq].len = a[p].len + 1;
        a[q].fa = a[np].fa = nq;
        for (; a[p].son[c] == q; p = a[p].fa) a[p].son[c] = nq;
      }
    }
  }
  void insert(char *s) {
    int i, n = strlen(s);
    for (i = 0; i < n; i++) add(s[i] - 'a');
    for (i = 1; i <= tot; i++)
      a[i].c.r = a[i].len, a[i].c.l = a[a[i].fa].len + 1;
  }
  int solve(int low, int high) {
    int p, l = 1, r = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= tot; i++) cnt[a[i].fa]++;
    for (int i = 1; i <= tot; i++)
      if (!cnt[i]) q[++r] = i;
    while (l <= r) {
      p = q[l++];
      if (p) {
        if (num[p] + a[p].q.size() < low) a[p].c.r = a[p].c.l - 1;
        if (num[p] > high) a[p].c.l = a[p].c.r + 1;
        while (num[p] < low - 1 && a[p].q.size()) num[p]++, a[p].q.pop();
        if (num[p] == low - 1 && a[p].q.size())
          a[p].c.r = min(a[p].c.r, a[p].q.top());
        while (num[p] < high && a[p].q.size()) num[p]++, a[p].q.pop();
        if (num[p] == high && a[p].q.size())
          a[p].c.l = max(a[p].c.r, a[p].q.top() + 1);
        while (a[p].q.size()) num[p]++, a[p].q.pop();
        num[a[p].fa] += num[p];
        if (!--cnt[a[p].fa]) q[++r] = a[p].fa;
      }
      while (a[p].q.size()) a[p].q.pop();
    }
  }
  int calc() {
    int i, ans = 0;
    for (i = 0; i <= tot; i++) ans += max(0, a[i].c.r - a[i].c.l + 1);
    return ans;
  }
  void draw() {
    for (int i = 0; i <= tot; i++) {
      printf("node:%d len=%d fa=%d size:(%d,%d) son:", i, a[i].len, a[i].fa,
             a[i].c.l, a[i].c.r);
      for (int j = 0; j < 26; j++)
        if (a[i].son[j]) printf("(%d,%d)", j, a[i].son[j]);
      cout << endl;
    }
    cout << endl;
  }
} SAM;
int main() {
  scanf("%s", s);
  n = strlen(s);
  SAM.insert(s);
  scanf("%d", &m);
  while (m--) {
    scanf("%s%d%d", s1, &l, &r);
    len = strlen(s1);
    for (i = j = k = 0; i < len; i++) {
      key = s1[i] - 'a';
      if (SAM.a[k].son[key])
        j++, k = SAM.a[k].son[key], SAM.a[k].q.push(j);
      else {
        while (k && !SAM.a[k].son[key]) k = SAM.a[k].fa;
        if (SAM.a[k].son[key]) {
          j = SAM.a[k].len + 1;
          k = SAM.a[k].son[key];
          SAM.a[k].q.push(j);
        } else
          j = k = 0;
      }
    }
    SAM.solve(l, r);
    memset(s1, 0, sizeof(s1));
  }
  printf("%d\n", SAM.calc() - 1);
  return 0;
}

```