CF316G3 Good Substrings

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

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

Print a single integer — the number of good substrings of string $ s $ .

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.