316_G1. Good Substrings_21688
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.*;
import java.util.*;

public class A {

	void run() throws IOException {
		String s = nl();
		int m = s.length();
		Set<String> h = new HashSet<String>();
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j <= m; j++) {
				h.add(s.substring(i, j));
			}
		}
		int ans = 0;
		int n = ni();
		String[] p = new String[n];
		int[] l = new int[n];
		int[] r = new int[n];

		for (int i = 0; i < n; i++) {
			p[i] = next();
			l[i] = ni();
			r[i] = ni();
		}
		for (String t : h) {
			int q = 0;
			for (int i = 0; i < n; i++) {
				int g = kmp(t, p[i]);
				if (l[i] <= g && g <= r[i]) {
					q++;
				}
			}
			if (q == n) {
				ans++;
			}
		}

		pw.println(ans);

	}

	int kmp(String p, String t) {
		int ans = 0;
		char[] a = p.toCharArray();
		char[] b = t.toCharArray();

		int x = a.length;
		int y = b.length;

		int len = x + y + 1;

		char[] s = new char[len];
		int[] z = new int[len];
		int l = 0, r = 0;

		for (int i = 0; i < x; i++)
			s[i] = a[i];
		for (int i = 0; i < y; i++)
			s[i + x + 1] = b[i];

		for (int i = 1; i < len; i++) {
			z[i] = Math.max(0, Math.min(r - i, z[i - l]));
			while (z[i] + i < len && s[z[i]] == s[i + z[i]])
				z[i]++;
			if (i + z[i] > r) {
				l = i;
				r = i + z[i];
			}
		}

		int q = 0;
		for (int i = x; i < len; i++)
			if (z[i] == x) {
				q++;
			}
		return q;
	}

	int[][] nm(int a_len, int a_hei) throws IOException {
		int[][] _a = new int[a_len][a_hei];
		for (int i = 0; i < a_len; i++)
			for (int j = 0; j < a_hei; j++)
				_a[i][j] = ni();
		return _a;
	}

	String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	int[] na(int a_len) throws IOException {
		int[] _a = new int[a_len];
		for (int i = 0; i < a_len; i++)
			_a[i] = ni();
		return _a;
	}

	int ni() throws IOException {
		return Integer.parseInt(next());
	}

	String nl() throws IOException {
		return br.readLine();
	}

	void tr(String debug) {
		if (!OJ)
			pw.println(" " + debug);
	}

	static PrintWriter pw;
	static BufferedReader br;
	static StringTokenizer st;
	static boolean OJ;

	public static void main(String[] args) throws IOException {
		long timeout = System.currentTimeMillis();
		OJ = System.getProperty("ONLINE_JUDGE") != null;
		pw = new PrintWriter(System.out);
		br = new BufferedReader(OJ ? new InputStreamReader(System.in) : new FileReader(new File("A.txt")));
		while (br.ready())
			new A().run();
		if (!OJ) {
			pw.println("----------------------------------");
			pw.println(System.currentTimeMillis() - timeout);
		}
		br.close();
		pw.close();
	}

}
