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>
using namespace std;
int mod1 = 1000000007;
int mod2;
unordered_set<unsigned long long> se;
inline pair<int, unsigned long long> operator*(
    pair<int, unsigned long long> a, pair<int, unsigned long long> b) {
  pair<int, unsigned long long> res = make_pair(0, 0);
  res.second = (a.second * 1ll * b.second);
  return res;
}
inline pair<int, unsigned long long> operator+(
    pair<int, unsigned long long> a, pair<int, unsigned long long> b) {
  pair<int, unsigned long long> res = make_pair(0, 0);
  res.second = a.second + b.second;
  return res;
}
inline pair<int, unsigned long long> operator-(
    pair<int, unsigned long long> a, pair<int, unsigned long long> b) {
  pair<int, unsigned long long> res = make_pair(0, 0);
  res.second = a.second - b.second;
  return res;
}
pair<int, unsigned long long> p[2010];
char s[2010];
pair<int, unsigned long long> h[2010];
pair<int, unsigned long long> hn[15][2010];
int le[15];
int len[15];
int ri[15];
int n, m;
inline int calc(int pos, int m, int v) {
  pair<int, unsigned long long> nowh = h[pos + m] - h[pos];
  int res = 0;
  for (int i = 0; i + m <= len[v]; ++i) {
    pair<int, unsigned long long> curh1 = nowh;
    pair<int, unsigned long long> curh2 = hn[v][i + m] - hn[v][i];
    if (i > pos)
      curh1 = curh1 * p[i - pos];
    else
      curh2 = curh2 * p[pos - i];
    res += (curh1 == curh2);
  }
  return res;
}
vector<pair<int, unsigned long long> > c;
vector<pair<int, unsigned long long> > good;
int main() {
  mod2 = 1000000111;
  p[0] = make_pair(1, 1);
  for (int i = (1); i < (2010); ++i) p[i] = p[i - 1] * make_pair(29, 29);
  h[0] = make_pair(0, 0);
  scanf("%s", &s);
  m = strlen(s);
  h[0] = make_pair(0, 0);
  for (int i = (0); i < (m); ++i) {
    pair<int, unsigned long long> curh =
        make_pair(s[i] - 'a' + 1, s[i] - 'a' + 1) * p[i];
    h[i + 1] = h[i] + curh;
  }
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) {
    scanf("%s%d%d", &s, &le[i], &ri[i]);
    int nm = strlen(s);
    len[i] = nm;
    hn[i][0] = make_pair(0, 0);
    for (int j = (0); j < (nm); ++j) {
      pair<int, unsigned long long> curh =
          make_pair(s[j] - 'a' + 1, s[j] - 'a' + 1) * p[j];
      hn[i][j + 1] = hn[i][j] + curh;
    }
  }
  int res = 0;
  for (int i = (0); i < (m); ++i) {
    c.clear();
    int best1 = 0;
    for (int j = (0); j < (n); ++j) {
      int l = 1, r = m - i;
      int best = 0;
      while (l <= r) {
        int mid = (l + r) / 2;
        if (calc(i, mid, j) >= le[j]) {
          best = mid;
          l = mid + 1;
        } else
          r = mid - 1;
      }
      c.push_back(make_pair(0, best));
      best = m - i + 1;
      l = 1, r = m - i;
      while (l <= r) {
        int mid = (l + r) / 2;
        if (calc(i, mid, j) <= ri[j]) {
          best = mid;
          r = mid - 1;
        } else
          l = mid + 1;
      }
      c.push_back(make_pair(best, m - i + 1));
    }
    int l = 0, r = m - i + 1;
    for (int j = (0); j < (c.size()); ++j) {
      l = ((l < c[j].first) ? (c[j].first) : (l));
      r = ((r < c[j].second) ? (r) : (c[j].second));
    }
    if (l == 0) l++;
    if (r == m - i + 1) r--;
    if (r >= l) {
      for (int j = (l); j < (r + 1); ++j) {
        pair<int, unsigned long long> now = h[i + j] - h[i];
        now = now * p[m + 5 - i];
        se.insert(now.second);
      }
    }
  }
  res = se.size();
  cout << res << endl;
  return 0;
}
