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.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.Writer;
import java.io.InputStream;

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

class TaskG3 {

    public int[] readToken(FastScanner in) {
        char[] c = in.next().toCharArray();
        int[] ret = new int[c.length];
        for (int i = 0; i < c.length; i++) {
            ret[i] = c[i] - 'a';
        }
        return ret;
    }

    static int[][] as;
    static int[] low;
    static int[] high;
    static SuffixAutomaton sa;
    static int[] terminal;
    static long[] dp1;
    static long[][] dp2;

    void dfs1(int v) {
        if (dp2[0][v] >= 0) return;
        for (int j = 0; j < dp2.length; j++) {
            dp2[j][v] = (terminal[v] >> j) & 1;
        }
        for (int i = 0; i < sa.link.length; i++) {
            int to = sa.link[i][v];
            if (to >= 0) {
                dfs1(to);
                for (int j = 0; j < dp2.length; j++) {
                    dp2[j][v] += dp2[j][to];
                }
            }
        }
    }

    void dfs2(int v) {
        if (dp1[v] >= 0) return;
        boolean ok = true;
        for (int i = 0; i < dp2.length;i++) {
            if (low[i] <= dp2[i][v] && dp2[i][v] <= high[i]) {

            } else {
                ok = false;
                break;
            }
        }
        if (v == 0) ok = false;
        if (ok) dp1[v] = 1; else dp1[v] = 0;
        for (int i = 0; i < sa.link.length; i++) {
            int to = sa.link[i][v];
            if (to >= 0) {
                dfs2(to);
                dp1[v] += dp1[to];
            }
        }
    }

    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        int[] ss = readToken(in);
        int n = in.nextInt();
        as = new int[n + 1][];
        low = new int[n + 1];
        high = new int[n + 1];
        low[0] = 1;
        high[0] = Integer.MAX_VALUE / 3;
        as[0] = ss;
        for (int i = 1; i <= n; i++) {
            as[i] = readToken(in);
            low[i] = in.nextInt();
            high[i] = in.nextInt();
        }
        sa = new SuffixAutomaton(as, 26);
        terminal = new int[sa.free];
        for (int i = 0; i <= n; i++) {
            int v = 0;
            for (int j : as[i]) {
                v = sa.link[j][v];
            }
            while (v >= 0) {
                terminal[v] |= 1 << i;
                v = sa.sufLink[v];
            }
        }
        dp1 = new long[terminal.length];
        dp2 = new long[n + 1][terminal.length];
        Arrays.fill(dp1, -1);
        for (long[] e : dp2) {
            Arrays.fill(e, -1);
        }
        dfs1(0);
        dfs2(0);
        out.println(dp1[0]);
    }
}

class FastScanner extends BufferedReader {

    public FastScanner(InputStream is) {
        super(new InputStreamReader(is));
    }

    public int read() {
        try {
            int ret = super.read();
//            if (isEOF && ret < 0) {
//                throw new InputMismatchException();
//            }
//            isEOF = ret == -1;
            return ret;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

    public String next() {
        StringBuilder sb = new StringBuilder();
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        if (c < 0) {
            return null;
        }
        while (c >= 0 && !isWhiteSpace(c)) {
            sb.appendCodePoint(c);
            c = read();
        }
        return sb.toString();
    }

    static boolean isWhiteSpace(int c) {
        return c >= 0 && c <= 32;
    }

    public int nextInt() {
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int ret = 0;
        while (c >= 0 && !isWhiteSpace(c)) {
            if (c < '0' || c > '9') {
                throw new NumberFormatException("digit expected " + (char) c
                        + " found");
            }
            ret = ret * 10 + c - '0';
            c = read();
        }
        return ret * sgn;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    }

class SuffixAutomaton {
    public int[][] link;
    public int[] sufLink;
    public int[] length;
    public int free;

    public SuffixAutomaton(int[][] a, int alphabet) {
        int all = 1;
        for (int[] i : a) {
            all += i.length;
        }
        all = all * 2 + 1;
        link = new int[alphabet][all];
        sufLink = new int[all];
        length = new int[all];
        for (int[] d : link) {
            Arrays.fill(d, -1);
        }
        Arrays.fill(sufLink, -1);
        free = 0;
        int root = newNode(0);
        for (int[] d : a) {
            int v = root;
            for (int i : d) {
                v = append(v, i);
            }
        }
    }

    int newNode(int len) {
        length[free] = len;
        return free++;
    }

    int copyNode(int v, int len) {
        length[free] = len;
        for (int i = 0; i < link.length; i++) {
            link[i][free] = link[i][v];
        }
        sufLink[free] = sufLink[v];
        return free++;
    }

    int append(int v, int c) {
        if (link[c][v] >= 0) {
            int q = link[c][v];
            if (length[q] == length[v] + 1) {
                return q;
            }
            int copy = copyNode(q, length[v] + 1);
            while (v >= 0 && link[c][v] == q) {
                link[c][v] = copy;
                v = sufLink[v];
            }
            sufLink[q] = copy;
            return copy;
        }
        int u = newNode(length[v] + 1);
        while (v >= 0 && link[c][v] < 0) {
            link[c][v] = u;
            v = sufLink[v];
        }
        if (v < 0) {
            sufLink[u] = 0;
            return u;
        }
        int q = link[c][v];
        if (length[q] == length[v] + 1) {
            sufLink[u] = q;
            return u;
        }
        int copy = copyNode(q, length[v] + 1);
        while (v >= 0 && link[c][v] == q) {
            link[c][v] = copy;
            v = sufLink[v];
        }
        sufLink[q] = sufLink[u] = copy;
        return u;
    }
}

class FastPrinter extends PrintWriter {

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

    public FastPrinter(Writer out) {
        super(out);
    }


}

