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;
struct SuffixAutomaton {
  struct Node {
    int link;
    map<char, int> next;
    int len;
    int dp_num_of_substr, dp_len_of_substr;
    int cnt;
    Node() {
      dp_num_of_substr = dp_len_of_substr = -1;
      link = -1;
      next = map<char, int>();
      len = cnt = 0;
    }
  };
  vector<Node> V;
  SuffixAutomaton(const string &S) {
    V.clear();
    V.push_back(Node());
    Node tmp;
    int last = 0;
    for (int i = 0; i < S.size(); ++i) {
      char c = S[i];
      int curr = V.size();
      V.push_back(Node());
      V.back().cnt = 1;
      V[curr].len = V[last].len + 1;
      int p;
      for (p = last; p != -1 && !V[p].next.count(c); p = V[p].link)
        V[p].next[c] = curr;
      if (p == -1) {
        V[curr].link = 0;
      } else {
        int q = V[p].next[c];
        if (V[p].len + 1 == V[q].len) {
          V[curr].link = q;
        } else {
          int clone = V.size();
          V.push_back(Node());
          V[clone].len = V[p].len + 1;
          V[clone].next = V[q].next;
          V[clone].link = V[q].link;
          for (; p != -1 && V[p].next[c] == q; p = V[p].link)
            V[p].next[c] = clone;
          V[q].link = V[curr].link = clone;
        }
      }
      last = curr;
    }
  }
  bool check(const string &P) {
    int v = 0;
    for (int i = 0; i < P.size(); ++i) {
      if (V[v].next.count(P[i]) == 0)
        return false;
      else
        v = V[v].next[P[i]];
    }
    return true;
  }
  int numberOfSubstrings(int v = 0) {
    if (V[v].next.size() == 0) return 1;
    if (V[v].dp_num_of_substr != -1) return V[v].dp_num_of_substr;
    int w = v != 0;
    for (map<char, int>::iterator it = V[v].next.begin(); it != V[v].next.end();
         ++it)
      w += numberOfSubstrings(it->second);
    return V[v].dp_num_of_substr = w;
  }
  int totalLengthOfSubstrings(int v = 0, int l = 0) {
    if (V[v].next.size() == 0) return 0;
    if (V[v].dp_len_of_substr != -1) return V[v].dp_len_of_substr;
    int w = 0;
    for (map<char, int>::iterator it = V[v].next.begin(); it != V[v].next.end();
         ++it)
      w += totalLengthOfSubstrings(it->second) + numberOfSubstrings(it->second);
    return V[v].dp_len_of_substr = w;
  }
  void computeOcurrences() {
    int ma = 0;
    for (int i = 0; i < V.size(); ++i) ma = max(ma, V[i].len);
    vector<vector<int> > TEMP(ma + 1, vector<int>());
    for (int i = 0; i < V.size(); ++i) TEMP[V[i].len].push_back(i);
    for (int i = ma; i >= 1; --i)
      for (int j = 0; j < TEMP[i].size(); ++j)
        V[V[TEMP[i][j]].link].cnt += V[TEMP[i][j]].cnt;
  }
  int numberOfOcurrences(const string &P) {
    int v = 0;
    for (int i = 0; i < P.size(); ++i)
      if (V[v].next.count(P[i]) == 0)
        return 0;
      else
        v = V[v].next[P[i]];
    return V[v].cnt;
  }
  int numberRotationOcurrences(const string &P) {
    string P2 = P + P;
    int v = 0;
    for (int i = 0; i < P.size(); ++i)
      if (V[v].next.count(P[i]) == 0)
        return 0;
      else
        v = V[v].next[P[i]];
    return V[v].cnt;
  }
};
void drawOccurrenc(int n, SuffixAutomaton &SA, string ST = "") {
  cout << n << " " << ST << " " << SA.V[n].cnt << endl;
  for (char i = 'a'; i <= 'z'; ++i) {
    if (SA.V[n].next.count(i)) {
      drawOccurrenc(SA.V[n].next[i], SA, ST + i);
    }
  }
}
int L[20], R[20];
int ans;
string STR;
void countOcurrences(int n, vector<int> IDX, SuffixAutomaton &SA,
                     vector<SuffixAutomaton> &V, int N, string STR = "") {
  for (char i = 'a'; i <= 'z'; ++i) {
    if (SA.V[n].next.count(i)) {
      int rc = 0;
      vector<int> IDX_C = vector<int>(N, -1);
      for (int j = 0; j < N; ++j) {
        int oc = 0;
        if (IDX[j] != -1) {
          if (V[j].V[IDX[j]].next.count(i))
            IDX_C[j] = V[j].V[IDX[j]].next[i];
          else
            IDX_C[j] = -1;
        }
      }
      for (int j = 0; j < N; ++j) {
        int oc = 0;
        if (IDX_C[j] != -1) oc = V[j].V[IDX_C[j]].cnt;
        if (oc >= L[j] && oc <= R[j]) rc++;
      }
      if (rc == N) ans++;
      countOcurrences(SA.V[n].next[i], IDX_C, SA, V, N, STR + string(1, i));
    }
  }
}
int main() {
  string A;
  cin >> A;
  SuffixAutomaton SA(A);
  SA.computeOcurrences();
  int N;
  cin >> N;
  vector<SuffixAutomaton> V;
  for (int i = 0; i < N; ++i) {
    string P;
    cin >> P;
    V.push_back(SuffixAutomaton(P));
    V.back().computeOcurrences();
    cin >> L[i];
    cin >> R[i];
  }
  vector<int> IDX;
  for (int i = 0; i < N; ++i) IDX.push_back(0);
  countOcurrences(0, IDX, SA, V, N);
  cout << ans << endl;
}
