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 java.util.Map;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.util.Set;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.util.HashSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author RiaD
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Reader in = new Reader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskG1 solver = new TaskG1();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskG1 {
    public void solve(int testNumber, Reader in, OutputWriter out) {
        String s = in.nextString();
        StringHash hashes = new SimpleInt64StringHash(s);

        int n = in.nextInt();

        int answer = 0;



        StringHash[] ts = new StringHash[n];
        int[] ls = new int[n];
        int[] rs = new int[n];
        for(int i = 0; i < n; ++i) {
            ts[i] = new SimpleInt64StringHash(in.nextString());
            ls[i] = in.nextInt();
            rs[i] = in.nextInt();
        }

        for(int len = 1; len <= s.length(); ++len) {

            Set<Long> availableStrings = new HashSet<Long>();
            for(int i = 0; i + len <= s.length(); ++i) {
                availableStrings.add(hashes.hash(i, i + len));
            }


            for(int i = 0; i < n; ++i){
                Counter<Long> timesAppeared = new Counter<Long>();

                StringHash inner = ts[i];
                int l = ls[i];
                int r = rs[i];

                for(int j = 0; j + len <= inner.length(); ++j)  {
                    timesAppeared.add(inner.hash(j, j + len));
                }

                if(l == 0) {
                    for (Map.Entry<Long, Long> entry : timesAppeared.entrySet()) {
                        if(entry.getValue() > r) {
                            availableStrings.remove(entry.getKey());
                        }
                    }
                }
                else {
                    Set<Long> nextStrings = new HashSet<Long>();
                    for (Map.Entry<Long, Long> entry : timesAppeared.entrySet()) {

                        if(entry.getValue() >= l && entry.getValue() <= r && availableStrings.contains(entry.getKey()))
                            nextStrings.add(entry.getKey());
                    }
                    availableStrings = nextStrings;
                }

            }

            answer += availableStrings.size();
        }

        out.println(answer);
    }
}

class Reader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public Reader(BufferedReader reader) {
        this.reader = reader;
    }

    public Reader(InputStream stream) {
        this(new BufferedReader(new InputStreamReader(stream)));
    }

    public String nextString() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    private String readLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

class OutputWriter extends PrintWriter {

    public OutputWriter(OutputStream out) {
        super(out);
    }

    public OutputWriter(java.io.Writer writer){
        super(writer);
    }

    }

interface StringHash {

    public long hash(int from, int to);

    public int length();

}

class SimpleInt64StringHash extends AbstractStringHash {
    private long[] hash;
    private static long[] powers;
    public static long multiplier = 97;

    public SimpleInt64StringHash(CharSequence string) {
        int length = string.length();
        ensureLength(length);
        hash = new long[length + 1];
        hash[0] = 0;
        for (int i = 0; i < length; ++i) {
            hash[i + 1] = hash[i] * multiplier + string.charAt(i);
        }
    }

    private static void ensureLength(int length) {
        if(powers != null && length + 1 <= powers.length)
            return;
        powers = new long[length + 1];
        powers[0] = 1;

        for (int i = 1; i <= length; ++i) {
            powers[i] = powers[i - 1] * multiplier;
        }
    }

    public long hash(int from, int to) {
        return hash[to] - hash[from] * powers[to - from];
    }

    public int length() {
        return hash.length - 1;
    }
}

class Counter<T> extends HashMap<T, Long> {
    public void add(T key) {
        add(key, 1);
    }

    public void add(T key, long value) {
        put(key, get(key) + value);
    }

    public Long get(Object key) {
        return containsKey(key) ? super.get(key) : 0;
    }

}

abstract class AbstractStringHash implements StringHash {

    }
