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.
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:16777216")
using namespace std;
int n, k, c, p, nn;
char S[600000];
vector<int> T;
vector<int> I;
int C[22][600000];
vector<pair<pair<int, int>, int> > Q;
int X[600000];
int P[600000];
int J[600000];
int Y[600000];
int L[600000];
long long R[600000];
int T1[600000 * 4];
int T2[600000 * 4];
int XX[600000];
int YY[600000];
int CC[600000];
int SS[600000][11];
int LL[64];
int RR[64];
vector<int> PP[600000];
void Set1(int j, int d, int i, int l, int r) {
  if (l == r)
    T1[i] = d;
  else {
    int m = (l + r) / 2;
    if (j <= m)
      Set1(j, d, i * 2, l, m);
    else
      Set1(j, d, i * 2 + 1, m + 1, r);
    T1[i] = max(T1[i * 2], T1[i * 2 + 1]);
  }
}
int Get1(int l, int r, int i, int tl, int tr) {
  if (l > r) return -1;
  if (l == tl && r == tr) return T1[i];
  int tm = (tl + tr) / 2;
  if (r <= tm) return Get1(l, r, i * 2, tl, tm);
  if (l > tm) return Get1(l, r, i * 2 + 1, tm + 1, tr);
  return max(Get1(l, tm, i * 2, tl, tm),
             Get1(tm + 1, r, i * 2 + 1, tm + 1, tr));
}
void Set2(int j, int d, int i, int l, int r) {
  if (l == r)
    T2[i] = d;
  else {
    int m = (l + r) / 2;
    if (j <= m)
      Set2(j, d, i * 2, l, m);
    else
      Set2(j, d, i * 2 + 1, m + 1, r);
    T2[i] = min(T2[i * 2], T2[i * 2 + 1]);
  }
}
int Get2(int l, int r, int i, int tl, int tr) {
  if (l > r) return n;
  if (l == tl && r == tr) return T2[i];
  int tm = (tl + tr) / 2;
  if (r <= tm) return Get2(l, r, i * 2, tl, tm);
  if (l > tm) return Get2(l, r, i * 2 + 1, tm + 1, tr);
  return min(Get2(l, tm, i * 2, tl, tm),
             Get2(tm + 1, r, i * 2 + 1, tm + 1, tr));
}
bool Cmp(int a, int b) {
  pair<int, int> aa;
  pair<int, int> bb;
  aa.first = C[p][a];
  aa.second = C[p][(a + n - (1 << p)) % n];
  bb.first = C[p][b];
  bb.second = C[p][(b + n - (1 << p)) % n];
  return aa < bb;
}
int G(int l, int r, int x) {
  if (l > r) return 0;
  return (SS[r][x] - (l == 0 ? 0 : SS[l - 1][x]));
}
bool F1(int pos, int x) {
  int l = -1, r = n;
  if (pos > 0) l = Get1(0, x - 1, 1, 0, 600000 - 1);
  if (pos < n - 1) r = Get2(0, x - 1, 1, 0, 600000 - 1);
  l++;
  r--;
  for (int i = (1); i < (nn + 1); ++i)
    if (G(l, r, i) < LL[i - 1]) return 0;
  return 1;
}
bool F2(int pos, int x) {
  int l = -1, r = n;
  if (pos > 0) l = Get1(0, x - 1, 1, 0, 600000 - 1);
  if (pos < n - 1) r = Get2(0, x - 1, 1, 0, 600000 - 1);
  l++;
  r--;
  for (int i = (1); i < (nn + 1); ++i)
    if (G(l, r, i) > RR[i - 1]) return 0;
  return 1;
}
bool F3(int pos, int x) {
  int l = -1, r = n;
  if (pos > 0) l = Get1(0, x - 1, 1, 0, 600000 - 1);
  if (pos < n - 1) r = Get2(0, x - 1, 1, 0, 600000 - 1);
  l++;
  r--;
  return G(l, pos, 0) == 1;
}
int main() {
  scanf("%s", S);
  int len = strlen(S);
  for (int j = (0); j < (len); ++j) {
    J[T.size()] = 0;
    CC[T.size()] = len - j;
    T.push_back(S[j] - 'a');
  }
  J[T.size()] = -1;
  T.push_back(1000000000);
  cin >> n;
  nn = n;
  for (int i = (1); i < (n + 1); ++i) {
    scanf("%s %d %d", S, &LL[i - 1], &RR[i - 1]);
    int len = strlen(S);
    for (int j = (0); j < (len); ++j) {
      J[T.size()] = i;
      CC[T.size()] = len - j;
      T.push_back(S[j] - 'a');
    }
    J[T.size()] = -1;
    T.push_back(1000000000 + i);
  }
  n = T.size();
  for (int i = (0); i < (n); ++i)
    Q.push_back(make_pair(make_pair(T[i], -1), i));
  sort(Q.begin(), Q.end());
  c = 0;
  for (int i = (0); i < (n); ++i) {
    if (i > 0 && Q[i].first != Q[i - 1].first) c++;
    C[0][Q[i].second] = c;
  }
  p = 0;
  while ((1 << (p + 1)) <= n) p++;
  for (int i = (1); i < (p + 1); ++i) {
    Q.clear();
    c = 0;
    for (int j = (0); j < (n); ++j)
      Q.push_back(make_pair(
          make_pair(C[i - 1][j], C[i - 1][(j + (1 << (i - 1))) % n]), j));
    sort(Q.begin(), Q.end());
    for (int j = (0); j < (n); ++j) {
      if (j > 0 && Q[j].first != Q[j - 1].first) c++;
      C[i][Q[j].second] = c;
    }
  }
  for (int i = (0); i < (n); ++i) I.push_back(i);
  sort(I.begin(), I.end(), Cmp);
  for (int i = (0); i < (n - 1); ++i) {
    X[i] = 0;
    int a = I[i];
    int b = I[i + 1];
    for (int j = p; j >= 0; j--)
      if (C[j][a] == C[j][b]) {
        X[i] += (1 << j);
        a += (1 << j);
        b += (1 << j);
        a %= n;
        b %= n;
      }
  }
  for (int i = n - 1; i > 0; i--) {
    Y[i] = 0;
    int a = I[i];
    int b = I[i - 1];
    for (int j = p; j >= 0; j--)
      if (C[j][a] == C[j][b]) {
        Y[i] += (1 << j);
        a += (1 << j);
        b += (1 << j);
        a %= n;
        b %= n;
      }
  }
  map<int, int> M;
  for (int i = (0); i < (n); ++i) {
    int id = I[i];
    P[i] = -1;
    if (J[id] == -1) continue;
    if (M.find(J[id]) != M.end()) P[i] = M[J[id]];
    M[J[id]] = i;
  }
  for (int i = (0); i < (600000 * 4); ++i) {
    T1[i] = -1;
    T2[i] = n;
  }
  for (int i = n - 1; i > 0; i--) {
    Set2(Y[i], i, 1, 0, 600000 - 1);
    PP[Y[i]].push_back(i);
  }
  for (int i = (0); i < (n); ++i) {
    if (i > 0)
      for (int j = (0); j < (nn + 1); ++j) SS[i][j] = SS[i - 1][j];
    if (J[I[i]] != -1) SS[i][J[I[i]]]++;
  }
  long long res = 0;
  for (int i = (0); i < (n); ++i) {
    if (i > 0) {
      PP[Y[i]].pop_back();
      if (!PP[Y[i]].empty()) {
        int x = PP[Y[i]].back();
        Set2(Y[i], x, 1, 0, 600000 - 1);
      } else
        Set2(Y[i], n, 1, 0, 600000 - 1);
    }
    int left, right, up;
    if (J[I[i]] == 0) {
      int Min = 1, Max = CC[I[i]];
      while (Min < Max) {
        int Mid = (Min + Max) / 2;
        if (Min + 1 == Max) Mid++;
        if (F1(i, Mid))
          Min = Mid;
        else
          Max = Mid - 1;
      }
      if (!F1(i, Min)) --Min;
      right = Min;
    }
    if (J[I[i]] == 0) {
      int Min = 1, Max = CC[I[i]];
      while (Min < Max) {
        int Mid = (Min + Max) / 2;
        if (F2(i, Mid))
          Max = Mid;
        else
          Min = Mid + 1;
      }
      if (!F2(i, Min)) ++Min;
      left = Min;
    }
    if (J[I[i]] == 0) {
      int Min = 1, Max = CC[I[i]];
      while (Min < Max) {
        int Mid = (Min + Max) / 2;
        if (F3(i, Mid))
          Max = Mid;
        else
          Min = Mid + 1;
      }
      if (!F3(i, Min)) ++Min;
      up = Min;
    }
    if (J[I[i]] == 0) {
      left = max(left, up);
      res += max(0, right - left + 1);
    }
    if (i < n - 1) Set1(X[i], i, 1, 0, 600000 - 1);
  }
  cout << res << endl;
  return 0;
}
