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.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;

public class G implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new G(), "", 256 * (1L << 20)).start();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            //    in = new BufferedReader(new FileReader("src/input.txt"));
            // out = new PrintWriter("output.txt");

            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    // solution
    void solve() throws IOException {
        String s = readString();
        int n = readInt();
        HashMap<State, Integer> states = new HashMap<>();

        for (int l = 0; l < s.length(); l++) {
            int h1 = 0;
            int h2 = 0;
            for (int r = l; r < s.length(); r++) {
                h1 = (h1 * multiply1 + s.charAt(r));
                if (h1 >= modulo1) {
                    h1 %= modulo1;
                }
                h2 = (h2 * multiply2 + s.charAt(r));
                if (h2 >= modulo2) {
                    h2 %= modulo2;
                }
                states.put(new State(h1, h2), 0);
            }
        }

        for (int i = 0; i < n; i++) {
            String p = readString();
            int from = readInt();
            int to = readInt();
            for (int l = 0; l < p.length(); l++) {
                int h1 = 0;
                int h2 = 0;
                for (int r = l; r < p.length(); r++) {
                    h1 = (h1 * multiply1 + p.charAt(r));
                    if (h1 >= modulo1) {
                        h1 %= modulo1;
                    }
                    h2 = (h2 * multiply2 + p.charAt(r));
                    if (h2 >= modulo2) {
                        h2 %= modulo2;
                    }
                    State state = new State(h1, h2);
                    Integer count = states.get(state);
                    if (count != null) {
                        states.put(state, count + 1);
                    }
                }
            }

            for (Iterator<Map.Entry<State, Integer>> it = states.entrySet().iterator(); it.hasNext();) {
                Map.Entry<State, Integer> entry = it.next();
                Integer q = entry.getValue();
                if (q < from) {
                    it.remove();
                } else if (q > to) {
                    it.remove();
                } else {
                    states.put(entry.getKey(), 0);
                }

            }
        }
        out.println(states.size());
    }
    static final int modulo1 = Integer.MAX_VALUE / 1021 - 41;
    static final int multiply1 = 102;
    static final int modulo2 = Integer.MAX_VALUE / 1049 - 21;
    static final int multiply2 = 131;

    class State {

        int h1;
        int h2;
        int cur;

        State(int h1, int h2) {
            this.h1 = h1;
            this.h2 = h2;
        }

        @Override
        public int hashCode() {
            return h1;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final State other = (State) obj;
            if (this.h1 != other.h1) {
                return false;
            }
            if (this.h2 != other.h2) {
                return false;
            }
            return true;
        }
    }
}