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 G {

	BufferedReader in;
	StringTokenizer stk;
	PrintWriter out;

	String next() throws IOException {
		while (stk == null || !stk.hasMoreTokens())
			stk = new StringTokenizer(in.readLine());
		return stk.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());
	}

	void solve() throws Exception {
		String s = next();
		int m = nextInt(), n = s.length();
		int l[] = new int[m];
		int r[] = new int[m];
		String a[] = new String[m];
		for (int i = 0; i < m; i++) {
			a[i] = next();
			l[i] = nextInt();
			r[i] = nextInt();
		}

		HashSet<Integer> pos[] = new HashSet[2001];
		for (int i = 0; i <= 2000; i++)
			pos[i] = new HashSet<Integer>();

		for (int i = 0; i < n; i++) {

			int ir = n;

			for (int k = 0; k < m; k++) {
				int L = i, R = n + 1;
				while (R - L > 1) {
					int M = (L + R) / 2;
					String chk = s.substring(i, M);
					if (count(chk, a[k]) < l[k]) {
						R = M;
					} else {
						L = M;
					}
				}
				ir = Math.min(ir, L);
			}

			int il = i + 1;

			for (int k = 0; k < m; k++) {
				int L = i, R = n + 1;
				while (R - L > 1) {
					int M = (L + R) / 2;
					String chk = s.substring(i, M);
					if (count(chk, a[k]) <= r[k]) {
						R = M;
					} else {
						L = M;
					}
				}
				il = Math.max(il, R);
			}

			// System.err.println(i + " " + il + " " + ir);

			// System.err.print(s.substring(i, il));
			// System.err.println(" - " + s.substring(i, ir));

			for (int j = il; j <= Math.min(ir, s.length()); j++) {
				pos[j - i].add(i);
				// str[j - i].add(s.substring(i, j));
			}
		}
		// for (String ss : str)
		// System.err.println(ss);
		long ans = 0;
		HashSet<String> str = new HashSet<String>();

		for (int i = 1; i <= 2000; i++) {
			str.clear();
			for (int p : pos[i]) {
				str.add(s.substring(p, p + i));
			}
			ans += str.size();
		}
		out.println(ans);
	}

	int count(String o, String chk) {
		int count = 0;
		for (int i = 0; i <= chk.length() - o.length(); i++) {
			boolean fit = true;
			for (int j = 0; j < o.length() && fit; j++)
				fit &= (o.charAt(j) == chk.charAt(i + j));
			if (fit)
				count++;
		}
		return count;
	}

	static class State {
		int length;
		int link;
		int endpos;
		int[] next = new int[256];
		{
			Arrays.fill(next, -1);
		}
		List<Integer> ilink = new ArrayList<Integer>(0);
	};

	State[] st;
	int size;
	int last;
	int lastp;

	void saExtend(char c) {
		int nlast = size++;
		st[nlast] = new State();
		st[nlast].length = st[last].length + 1;
		st[nlast].endpos = st[last].length;
		int p;
		for (p = last; p != -1 && st[p].next[c] == -1; p = st[p].link) {
			st[p].next[c] = nlast;
		}
		if (p == -1) {
			st[nlast].link = 0;
		} else {
			int q = st[p].next[c];
			if (st[p].length + 1 == st[q].length)
				st[nlast].link = q;
			else {
				int clone = size++;
				st[clone] = new State();
				st[clone].length = st[p].length + 1;
				st[clone].next = st[q].next.clone();
				st[clone].link = st[q].link;
				for (; p != -1 && st[p].next[c] != -1 && st[p].next[c] == q; p = st[p].link)
					st[p].next[c] = clone;
				st[q].link = clone;
				st[nlast].link = clone;
				st[clone].endpos = -1;
			}
		}
		last = nlast;
	}

	public void buildSA(String s) {
		int n = s.length();
		st = new State[Math.max(2, 2 * n - 1)];
		st[0] = new State();
		st[0].link = -1;
		st[0].endpos = -1;
		last = 0;
		size = 1;
		for (char x : s.toCharArray()) {
			saExtend(x);
		}
		for (int i = 1; i < size; i++) {
			st[st[i].link].ilink.add(i);
		}
	}

	public String lcs(String a, String b) {
		buildSA(a);
		int p = 0;
		lastp = 0;
		int len = 0;
		int best = 0;
		int bestpos = -1;
		for (int i = 0; i < b.length(); ++i) {
			char cur = b.charAt(i);
			if (st[p].next[cur] == -1) {
				for (; p != -1 && st[p].next[cur] == -1; p = st[p].link) {
				}
				if (p == -1) {
					p = 0;
					len = 0;
					continue;
				}
				len = st[p].length;
			}
			++len;
			p = st[p].next[cur];
			if (best < len) {
				best = len;
				bestpos = i;
				lastp = p;
			}
		}
		return b.substring(bestpos - best + 1, bestpos + 1);
	}

	public int occurrences(String needle, String haystack) {
		String common = lcs(haystack, needle);
		if (!common.equals(needle))
			return 0;
		List<Integer> list = new ArrayList<Integer>();
		return dfs(lastp, needle.length());

	}

	int dfs(int p, int len) {
		int ans = 0;
		if (st[p].endpos != -1 || p == 0)
			ans++;
		for (int x : st[p].ilink)
			ans += dfs(x, len);
		return ans;
	}

	void run() {
		try {
			Locale.setDefault(Locale.US);
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
			solve();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public static void main(String[] args) {
		new G().run();
	}

}