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.
import static java.lang.Math.* ;
import static java.util.Arrays.* ;

import java.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main
{

    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        char [] s = sc.next().toCharArray() ;
        SuffixAutomaton sa = new SuffixAutomaton(s) ;

        int n = sc.nextInt() ;
        int ans = 0 ;

        int [] minLen = new int [sa.idx + 1] ;
        int [] maxLen = new int [sa.idx + 1] ;

        for(int i = 1 ; i <= sa.idx ; i++)
        {
                minLen[i] = sa.len[sa.link[i]] + 1 ;
                maxLen[i] = sa.len[i] ;
        }
        while(n-->0)
        {
            char [] p = sc.next().toCharArray() ;

            SuffixAutomaton curr = new SuffixAutomaton(p) ;

            int l = sc.nextInt() , r = sc.nextInt() ;

            for(int v = 1 ; v <= sa.idx; v ++)
            {
                int end = sa.endPos[v] ;
                while(minLen[v] <= maxLen[v])
                {
                    int state = 0 ;
                    for(int from = end - minLen[v] + 1 ; from <= end && state != -1; from ++)
                        if (curr.next[s[from] - 'a'][state] != 0)
                            state = curr.next[s[from] - 'a'][state];
                        else
                            state = -1;
                    
                    int occ = state == -1 ? 0 : curr.cnt[state] ;
                    if(l <= occ && occ <= r) break;
                    minLen[v] ++ ;
                }
                while(minLen[v] <= maxLen[v])
                {
                    int state = 0 ;
                    for(int from = end - maxLen[v] + 1 ; from <= end && state != -1; from ++)
                        if (curr.next[s[from] - 'a'][state] != 0)
                            state = curr.next[s[from] - 'a'][state];
                        else
                            state = -1;
                    
                    int occ = state == -1 ? 0 : curr.cnt[state] ;
                    if(l <= occ && occ <= r) break;
                    maxLen[v] -- ;
                }
            }
        }

        for(int v = 1 ; v <= sa.idx ; v++)
            ans += max(0, maxLen[v] - minLen[v] + 1);
        out.println(ans);
        out.flush();
        out.close();
    }
    class SuffixAutomaton
    {
        int[] link, len , cnt;
        int [][] next ;
        boolean [] isClone ;
        int lst, idx;
        int [] endPos ;

        SuffixAutomaton(char[] s)
        {
            int n = s.length;
            link = new int[n<<1];
            len = new int[n<<1];
            next = new int [26][n << 1] ;
            cnt = new int [n << 1] ;
            endPos = new int [n << 1] ;
            isClone = new boolean[n << 1] ;
            int ix = 0 ;
            for(char c: s)
                addLetter(c - 'a' , ix ++);

            Integer [] id = new Integer[idx + 1] ;

            for(int i = 0 ; i <= idx ; i++) {
                id[i] = i;
                isClone[i] = cnt[i] == 0;
            }

            sort(id , (x , y)->len[y] - len[x]);

            for(int v : id)
                cnt[link[v]] += cnt[v] ;
        }

        void addLetter(int c , int ix)
        {
            int cur = ++idx, p = lst;
            endPos[cur] = ix ;
            while(next[c][p] == 0) { next[c][p] = cur; p = link[p]; }
            cnt[cur] = 1 ;
            int q = next[c][p];
            if(q != cur)
                if(len[q] == len[p] + 1)
                    link[cur] = q;
                else
                {
                    int clone = ++idx;
                    len[clone] = len[p] + 1;
                    link[clone] = link[q];
                    endPos[clone] = endPos[q] ;
                    for(int i = 0 ; i < 26 ; i++)
                        next[i][clone] = next[i][q] ;
                    link[cur] = link[q] = clone;
                    while(next[c][p] == q) { next[c][p] =  clone; p = link[p]; }
                }
            len[cur] = len[lst] + 1;
            lst = cur;
        }
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        Scanner(String path) throws Exception
        {
            br = new BufferedReader(new FileReader(path)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws Exception { return Integer.parseInt(next()); }

        long nextLong() throws Exception { return Long.parseLong(next()); }

        double nextDouble() throws Exception { return Double.parseDouble(next());}
    }

    public static void main (String [] args) throws Exception {(new Main()).main();}

}