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 = s 1 s 2 ... s | s | ( | s | is a length of s ) is string s l s l + 1 ... s r . 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 . 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 p i , l i , r i , separated by single spaces ( 0 ≤ l i ≤ r i ≤ | p i | ). 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 th