Good Substrings

题意翻译

给出 $n$ 个限制，每个限制包含 3 个参数 $T,l,r$, 一个字符串满足当前限制当且仅当这个字符串在 T 中的出现次数在 $[l,r]$ 之间。 现在给你一个字符串 $S$ ,问你 $S$ 的所有本质不同的子串中有多少个满足所有限制。

题目描述

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 the maximum length of string $ p $ is $ <=50000 $ .

输出格式

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

输入输出样例

输入样例 #1

aaab
2
aa 0 0
aab 1 1

输出样例 #1

3

输入样例 #2

ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1

输出样例 #2

2

输入样例 #3

a
0

输出样例 #3

1

说明

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.