Smart Beaver 最近对一个新的文字游戏感兴趣。要点如下:统计某个字符串 s 中不同的好子串的数量。为了确定一根绳子是否好,游戏使用规则。总共有n条规则。每个规则由一组三个 (p, l, r) 描述,其中 p 是字符串,l 和 r (l ≤ r) 是整数。如果字符串 t 在字符串 p 中出现的次数介于 l 和 r 之间(包含这两个值),我们就说字符串 t 符合规则 (p, l, r)。例如,字符串“ab”,符合规则(“ab”, 1, 2)和(“aab”, 0, 1),但不符合规则(“cd”, 1, 2)和(“abab”, 0, 1)。
字符串 s = s1s2... s|s| 的子串 s[l... r] (1 ≤ l ≤ r ≤ |s|) (|s| 是 s 的长度)是字符串 slsl + 1... sr。
将字符串 p 中字符串 t 的出现次数视为多对整数 l, r (1 ≤ l ≤ r ≤ |p|),使得 p[l...r] = t。
如果字符串 t 符合所有 n 个规则,我们就说它是好的。聪明的海狸请你帮他写一个程序,可以计算字符串 s 中不同的好子串的数量。两个子串 s[x... y] 和 s[z... w] 被视为不同,当且仅当 s[x... y] ≠ s[z... w]。
输入
第一行包含字符串 s。第二行包含整数n。接下来的 n 行包含规则,每行一个。这些行中的每一行都包含一个字符串和两个整数 pi、li、ri,用单个空格分隔 (0 ≤ li ≤ ri ≤ |pi|)。保证所有给定的字符串非空且仅包含小写英文字母。
得分 30 分的输入限制为(子问题 G1):
- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 200。
得分 70 分的输入限制为(子问题 G1+G2):
- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 2000。
获得 100 分的输入限制为(子问题 G1+G2+G3):
- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 50000。
输出
打印一个整数——字符串 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
注意
第一个样本测试中有三个好的子字符串:《aab》、《ab》和《b》。
在第二个测试中,只有子字符串“e”和“t”是好的。