#include <bits/stdc++.h>
using namespace std;
const int CNT = 2;
const int A = 27;
const int N = (int)1e5;
const int M = (int)2e7;
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
const int pr = 12381;
char str[N], p[N], limit[N];
int leftB[10][N], rightB[10][N];
bool used[M];
int mv = 0;
struct Node {
  int len;
  Node *suff;
  bool term;
  int id;
  int cnt;
  Node *go[A];
  Node() {
    cnt = 0;
    id = mv++;
    len = 0;
    term = false;
    suff = NULL;
    for (int i = 0; i < A; i++) go[i] = NULL;
  }
  Node(int len_) {
    cnt = 0;
    id = mv++;
    len = len_;
    term = false;
    suff = NULL;
    for (int i = 0; i < A; i++) go[i] = NULL;
  }
};
struct PolyHash {
  int p[CNT];
  PolyHash() {}
  PolyHash(long long x) {
    for (int i = 0; i < CNT; i++) p[i] = (x % (long long)mod[i]);
  }
  void operator+=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] += a.p[i];
      if (p[i] >= mod[i]) p[i] -= mod[i];
    }
  }
  void operator*=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] = ((long long)p[i] * (long long)a.p[i]) % (long long)mod[i];
    }
  }
  void operator-=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] -= a.p[i];
      if (p[i] < 0) p[i] += mod[i];
    }
  }
  bool operator<(const PolyHash &a) const {
    for (int i = 0; i < CNT; i++) {
      if (a.p[i] != p[i]) return p[i] < a.p[i];
    }
    return false;
  }
} Hash[N], deg[N];
set<PolyHash> allStr;
typedef Node *Node_ptr;
struct SuffixA {
  Node_ptr root;
  Node_ptr last;
  SuffixA() {
    root = new Node();
    last = root;
  }
};
int getId(Node_ptr v) {
  if (v == NULL) return -1;
  return v->id;
}
void printTree(Node_ptr v) {
  if (v == NULL || used[v->id]) return;
  used[v->id] = 1;
  printf("ID = %d, suff = %d\nGo: ", v->id, getId(v->suff));
  for (int i = 0; i < 3; i++) {
    printf("%c:%d ", ('a' + i), getId((v->go)[i]));
  }
  puts("");
  for (int i = 0; i < 3; i++) printTree((v->go)[i]);
}
Node_ptr addChar(int c, Node_ptr root, Node_ptr last) {
  Node_ptr newL = new Node(last->len + 1);
  Node_ptr p;
  for (p = last; p != NULL && (p->go)[c] == NULL; p = p->suff)
    (p->go)[c] = newL;
  if (p == NULL)
    newL->suff = root;
  else {
    Node_ptr q = (p->go)[c];
    if (q->len == p->len + 1)
      newL->suff = q;
    else {
      Node_ptr clone = new Node(p->len + 1);
      for (int i = 0; i < A; i++) (clone->go)[i] = (q->go)[i];
      for (; p != NULL && (p->go)[c] == q; p = p->suff) (p->go)[c] = clone;
      clone->suff = q->suff;
      newL->suff = q->suff = clone;
    }
  }
  return newL;
}
SuffixA buildSuffixA(char *s, int len) {
  SuffixA res = SuffixA();
  for (int i = 0; i < len; i++)
    res.last = addChar(s[i] - 'a', res.root, res.last);
  return res;
}
void calcTerm(SuffixA cur) {
  Node_ptr p = cur.last;
  while (p != NULL) {
    p->term = true;
    p = p->suff;
  }
}
void calcCnt(Node_ptr v) {
  if (used[v->id]) return;
  if (v->term) v->cnt = 1;
  used[v->id] = 1;
  for (int i = 0; i < A; i++) {
    Node_ptr to = (v->go)[i];
    if (to != NULL) {
      calcCnt(to);
      v->cnt += to->cnt;
    }
  }
}
void calcCnt(SuffixA cur) { calcCnt(cur.root); }
int getCnt(Node_ptr v1, Node_ptr v2, int c) {
  return ((v1->go)[c]->cnt) - ((v2->go)[c]->cnt);
}
Node_ptr getPosWithoutLast(Node_ptr v, int len) {
  if (v->suff == NULL) return v;
  if ((v->suff)->len == len - 1) return v->suff;
  return v;
}
void updateLimitPos(SuffixA lim, SuffixA strA, char *s, int len, int l, int r,
                    int *lB, int *rB) {
  Node_ptr limPos = lim.root;
  Node_ptr strPos = strA.root;
  int curB = 0;
  for (int i = 0; i < len; i++) {
    curB = max(i, curB);
    while (curB < len && getCnt(limPos, strPos, s[curB] - 'a') > r) {
      limPos = (limPos->go)[s[curB] - 'a'];
      strPos = (strPos->go)[s[curB] - 'a'];
      curB++;
    }
    lB[i] = curB - 1;
    limPos = getPosWithoutLast(limPos, curB - i);
    strPos = getPosWithoutLast(strPos, curB - i);
  }
  limPos = lim.root;
  strPos = strA.root;
  curB = 0;
  for (int i = 0; i < len; i++) {
    curB = max(i, curB);
    while (curB < len && getCnt(limPos, strPos, s[curB] - 'a') >= l) {
      cerr << getCnt(limPos, strPos, s[curB] - 'a') << ":" << l << endl;
      ;
      limPos = (limPos->go)[s[curB] - 'a'];
      strPos = (strPos->go)[s[curB] - 'a'];
      curB++;
    }
    rB[i] = curB - 1;
    limPos = getPosWithoutLast(limPos, curB - i);
    strPos = getPosWithoutLast(strPos, curB - i);
  }
  cerr << "----------------" << endl;
}
void calcDeg() {
  deg[0] = PolyHash(1);
  for (int i = 1; i < N; i++) {
    deg[i] = PolyHash(pr);
    deg[i] *= deg[i - 1];
  }
}
void calcHash(char *s, int len) {
  Hash[0] = PolyHash(s[0] - 'a' + 1);
  for (int i = 1; i < len; i++) {
    Hash[i] = PolyHash(s[i] - 'a' + 1);
    Hash[i] *= deg[i];
    Hash[i] += Hash[i - 1];
  }
}
PolyHash getHash(int a, int b) {
  PolyHash res = Hash[b];
  if (a > 0) res -= Hash[a - 1];
  res *= deg[N - a - 1];
  return res;
}
int main() {
  int n;
  scanf("%s%d", str, &n);
  int lenStr = strlen(str);
  calcDeg();
  calcHash(str, lenStr);
  SuffixA strA = buildSuffixA(str, lenStr);
  calcTerm(strA);
  calcCnt(strA);
  for (int i = 0; i < n; i++) {
    int l, r;
    scanf(" %s%d%d", p, &l, &r);
    int lenP = strlen(p);
    copy(str, str + lenStr, limit);
    limit[lenStr] = 'z' + 1;
    copy(p, p + lenP, limit + lenStr + 1);
    limit[lenStr + lenP + 1] = 0;
    SuffixA curA = buildSuffixA(limit, lenStr + lenP + 1);
    calcTerm(curA);
    calcCnt(curA);
    updateLimitPos(curA, strA, str, lenStr, l, r, leftB[i], rightB[i]);
  }
  int ans = 0;
  for (int i = 0; i < lenStr; i++) {
    int curL = i - 1, curR = lenStr - 1;
    for (int s = 0; s < n; s++) {
      curL = max(curL, leftB[s][i]);
      curR = min(curR, rightB[s][i]);
    }
    for (int s = curL + 1; s <= curR; s++) {
      PolyHash curH = getHash(i, s);
      if (allStr.find(curH) == allStr.end()) {
        ans++;
        allStr.insert(curH);
      }
    }
  }
  printf("%d", 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;
const int CNT = 2;
const int A = 27;
const int N = (int)1e5;
const int M = (int)2e7;
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
const int pr = 12381;
char str[N], p[N], limit[N];
int leftB[10][N], rightB[10][N];
bool used[M];
int mv = 0;
struct Node {
  int len;
  Node *suff;
  bool term;
  int id;
  int cnt;
  Node *go[A];
  Node() {
    cnt = 0;
    id = mv++;
    len = 0;
    term = false;
    suff = NULL;
    for (int i = 0; i < A; i++) go[i] = NULL;
  }
  Node(int len_) {
    cnt = 0;
    id = mv++;
    len = len_;
    term = false;
    suff = NULL;
    for (int i = 0; i < A; i++) go[i] = NULL;
  }
};
struct PolyHash {
  int p[CNT];
  PolyHash() {}
  PolyHash(long long x) {
    for (int i = 0; i < CNT; i++) p[i] = (x % (long long)mod[i]);
  }
  void operator+=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] += a.p[i];
      if (p[i] >= mod[i]) p[i] -= mod[i];
    }
  }
  void operator*=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] = ((long long)p[i] * (long long)a.p[i]) % (long long)mod[i];
    }
  }
  void operator-=(const PolyHash &a) {
    for (int i = 0; i < CNT; i++) {
      p[i] -= a.p[i];
      if (p[i] < 0) p[i] += mod[i];
    }
  }
  bool operator<(const PolyHash &a) const {
    for (int i = 0; i < CNT; i++) {
      if (a.p[i] != p[i]) return p[i] < a.p[i];
    }
    return false;
  }
} Hash[N], deg[N];
set<PolyHash> allStr;
typedef Node *Node_ptr;
struct SuffixA {
  Node_ptr root;
  Node_ptr last;
  SuffixA() {
    root = new Node();
    last = root;
  }
};
int getId(Node_ptr v) {
  if (v == NULL) return -1;
  return v->id;
}
void printTree(Node_ptr v) {
  if (v == NULL || used[v->id]) return;
  used[v->id] = 1;
  printf("ID = %d, suff = %d\nGo: ", v->id, getId(v->suff));
  for (int i = 0; i < 3; i++) {
    printf("%c:%d ", ('a' + i), getId((v->go)[i]));
  }
  puts("");
  for (int i = 0; i < 3; i++) printTree((v->go)[i]);
}
Node_ptr addChar(int c, Node_ptr root, Node_ptr last) {
  Node_ptr newL = new Node(last->len + 1);
  Node_ptr p;
  for (p = last; p != NULL && (p->go)[c] == NULL; p = p->suff)
    (p->go)[c] = newL;
  if (p == NULL)
    newL->suff = root;
  else {
    Node_ptr q = (p->go)[c];
    if (q->len == p->len + 1)
      newL->suff = q;
    else {
      Node_ptr clone = new Node(p->len + 1);
      for (int i = 0; i < A; i++) (clone->go)[i] = (q->go)[i];
      for (; p != NULL && (p->go)[c] == q; p = p->suff) (p->go)[c] = clone;
      clone->suff = q->suff;
      newL->suff = q->suff = clone;
    }
  }
  return newL;
}
SuffixA buildSuffixA(char *s, int len) {
  SuffixA res = SuffixA();
  for (int i = 0; i < len; i++)
    res.last = addChar(s[i] - 'a', res.root, res.last);
  return res;
}
void calcTerm(SuffixA cur) {
  Node_ptr p = cur.last;
  while (p != NULL) {
    p->term = true;
    p = p->suff;
  }
}
void calcCnt(Node_ptr v) {
  if (used[v->id]) return;
  if (v->term) v->cnt = 1;
  used[v->id] = 1;
  for (int i = 0; i < A; i++) {
    Node_ptr to = (v->go)[i];
    if (to != NULL) {
      calcCnt(to);
      v->cnt += to->cnt;
    }
  }
}
void calcCnt(SuffixA cur) { calcCnt(cur.root); }
int getCnt(Node_ptr v1, Node_ptr v2, int c) {
  return ((v1->go)[c]->cnt) - ((v2->go)[c]->cnt);
}
Node_ptr getPosWithoutLast(Node_ptr v, int len) {
  if (v->suff == NULL) return v;
  if ((v->suff)->len == len - 1) return v->suff;
  return v;
}
void updateLimitPos(SuffixA lim, SuffixA strA, char *s, int len, int l, int r,
                    int *lB, int *rB) {
  Node_ptr limPos = lim.root;
  Node_ptr strPos = strA.root;
  int curB = 0;
  for (int i = 0; i < len; i++) {
    curB = max(i, curB);
    while (curB < len && getCnt(limPos, strPos, s[curB] - 'a') > r) {
      limPos = (limPos->go)[s[curB] - 'a'];
      strPos = (strPos->go)[s[curB] - 'a'];
      curB++;
    }
    lB[i] = curB - 1;
    limPos = getPosWithoutLast(limPos, curB - i);
    strPos = getPosWithoutLast(strPos, curB - i);
  }
  limPos = lim.root;
  strPos = strA.root;
  curB = 0;
  for (int i = 0; i < len; i++) {
    curB = max(i, curB);
    while (curB < len && getCnt(limPos, strPos, s[curB] - 'a') >= l) {
      cerr << getCnt(limPos, strPos, s[curB] - 'a') << ":" << l << endl;
      ;
      limPos = (limPos->go)[s[curB] - 'a'];
      strPos = (strPos->go)[s[curB] - 'a'];
      curB++;
    }
    rB[i] = curB - 1;
    limPos = getPosWithoutLast(limPos, curB - i);
    strPos = getPosWithoutLast(strPos, curB - i);
  }
  cerr << "----------------" << endl;
}
void calcDeg() {
  deg[0] = PolyHash(1);
  for (int i = 1; i < N; i++) {
    deg[i] = PolyHash(pr);
    deg[i] *= deg[i - 1];
  }
}
void calcHash(char *s, int len) {
  Hash[0] = PolyHash(s[0] - 'a' + 1);
  for (int i = 1; i < len; i++) {
    Hash[i] = PolyHash(s[i] - 'a' + 1);
    Hash[i] *= deg[i];
    Hash[i] += Hash[i - 1];
  }
}
PolyHash getHash(int a, int b) {
  PolyHash res = Hash[b];
  if (a > 0) res -= Hash[a - 1];
  res *= deg[N - a - 1];
  return res;
}
int main() {
  int n;
  scanf("%s%d", str, &n);
  int lenStr = strlen(str);
  calcDeg();
  calcHash(str, lenStr);
  SuffixA strA = buildSuffixA(str, lenStr);
  calcTerm(strA);
  calcCnt(strA);
  for (int i = 0; i < n; i++) {
    int l, r;
    scanf(" %s%d%d", p, &l, &r);
    int lenP = strlen(p);
    copy(str, str + lenStr, limit);
    limit[lenStr] = 'z' + 1;
    copy(p, p + lenP, limit + lenStr + 1);
    limit[lenStr + lenP + 1] = 0;
    SuffixA curA = buildSuffixA(limit, lenStr + lenP + 1);
    calcTerm(curA);
    calcCnt(curA);
    updateLimitPos(curA, strA, str, lenStr, l, r, leftB[i], rightB[i]);
  }
  int ans = 0;
  for (int i = 0; i < lenStr; i++) {
    int curL = i - 1, curR = lenStr - 1;
    for (int s = 0; s < n; s++) {
      curL = max(curL, leftB[s][i]);
      curR = min(curR, rightB[s][i]);
    }
    for (int s = curL + 1; s <= curR; s++) {
      PolyHash curH = getHash(i, s);
      if (allStr.find(curH) == allStr.end()) {
        ans++;
        allStr.insert(curH);
      }
    }
  }
  printf("%d", ans);
  return 0;
}

```