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.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;

;

public class Main {

	public static void main(String[] args) {
		try {
			if (new File("input.txt").exists())
				System.setIn(new FileInputStream("input.txt"));
		} catch (Exception e) {
		}
		try {
			new Main().run();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		in.close();
		out.close();
	}

	void solve() throws IOException {
		String s = nextToken();
		int len = s.length();
		int n = nextInt();
		String a[] = new String[n];
		int min[] = new int[n + 1];
		int max[] = new int[n + 1];
		min[0] = 1;
		max[0] = Integer.MAX_VALUE;
		
		for(int i = 0; i < n; i++){
			a[i] = nextToken();
			min[i + 1] = nextInt();
			max[i + 1] = nextInt();
			len += a[i].length();
		}
		SA sa = new SA();
		sa.saInit();
		sa.saExtend(s, 0);
		int dels[] = new int[n];
		if(n > 0)
			dels[0] = 200;
		for(int i = 1; i < n; i++)
			dels[i] = dels[i - 1] + 1;
		
		for(int i = 0; i < n; i++){
			sa.saExtend((char)dels[i], -1);
			sa.saExtend(a[i], i + 1);
		}
		
		sa.pushCnt();
		out.println(sa.getAns(min, max, n + 1));
		
	}

	class SA {
		final int SIZE = 50000 * 11;
		
		int maxV = 2 * SIZE;// 2 * n;
		int maxE = 3 * SIZE;// 3 * n;
		int sz, last;
		int link[] = new int[maxV];
		int len[] = new int[maxV];
		boolean cloned[] = new boolean[maxV];
		saMultiList next = new saMultiList(maxV, maxE);
		int cnt[][] = new int[SIZE][11];
		
		
		void saInit() {
			sz = 1;
			last = len[0] = 0;
			link[0] = -1;
		}
		
		
		public void pushCnt() {
			int deg[] = new int[sz];
			for(int i = 0; i < sz; i++)
				if(link[i] != -1)
					deg[link[i]]++;
			int qu[] = new int[sz];
			int h = 0, t = 0;
			for(int i = 0; i < sz; i++)
				if(deg[i] == 0)
					qu[t++] = i;
					
			while(h < t){
				int v = qu[h++];
				int pv = link[v];
				if(pv != -1){
					for(int id = 0; id < 11; id++)
						cnt[pv][id] += cnt[v][id];
					deg[pv]--;
					if(deg[pv] == 0)
						qu[t++] = pv;
				}
			}
		}
		
		public long getAns(int min[], int max[], int n){
			long ret = 0;
			for(int v = 1; v < sz; v++){
				boolean good = true;
				for(int id = 0; good &&id < n; id++)
					good &= min[id] <= cnt[v][id] && cnt[v][id] <= max[id];
					
				if(good){
//					System.err.println(Arrays.toString(Arrays.copyOf(cnt[v], n)));
					ret += len[v] - len[link[v]];
//					System.err.println("add " + len[v] + " | " +  cloned[v] + " " + link[v]);
				}
			}
//			System.err.println(Arrays.toString());
			return ret;
		}
		
		
		void saExtend(String s, int type){
//			System.err.println("extend " + s + " | " + type);
			for(int i = 0; i < s.length(); i++)
				saExtend(s.charAt(i), type);
		}

		void saExtend(char c, int typeS) {
			int cur = sz++;
			if(typeS != -1)
				cnt[cur][typeS] = 1;
			int p = last;
			len[cur] = len[last] + 1;
			int ch = c - 'a';
			// - 'A'
			for (; p != -1 && next.get(p, ch) == -1; p = link[p])
				next.add(p, cur, ch);
			if (p == -1) {
				link[cur] = 0;
			} else {
				int q = next.get(p, ch);
				if (len[q] == len[p] + 1) {
					link[cur] = q;
				} else {
					int clone = sz++;
					len[clone] = len[p] + 1;
					for (int j = next.head[q]; j != 0; j = next.next[j])
						next.add(clone, next.vert[j], next.symbol[j]);
					link[clone] = link[q];
					for (; p != -1 && next.get(p, ch) == q; p = link[p])
						next.replace(p, clone, ch);
					link[cur] = link[q] = clone;
				}
			}
			last = cur;
		}

		
	}
	
	class saMultiList{
		int[] prev, head, vert, next, symbol;
		int cnt;
		public saMultiList(int h, int s) {
			s++;
			head = new int[h];
			vert = new int[s];
			next = new int[s];
			symbol = new int[s];
			cnt = 1;
		}
		void add(int v, int nv, int ch){
			vert[cnt] = nv;
			symbol[cnt] = ch;
			next[cnt] = head[v];
			head[v] = cnt++;
		}
		void replace(int v, int nv, int ch){
			for(int j = head[v]; j != 0; j = next[j]){
				if(symbol[j] == ch){
					vert[j] = nv;
					return;
				}
			}
			throw new RuntimeException();
		}
		int get(int v, int ch){
			for(int j = head[v]; j != 0; j = next[j]){
				if(symbol[j] == ch){
					return vert[j];
				}
			}
			return -1;
		}
	}
	
	
	
	/* Utils */
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

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

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}

}
