Katya 最近开始发明编程任务并准备自己的竞赛。她不喜欢的是无聊和简单的约束。 Katya 厌倦了所有这些“N 不超过一千”和“ai 的总和不超过一百万”,她决定想出一些更复杂的东西。
Katya 写的最后一个问题涉及字符串。输入是一串小拉丁字母。为了让语句变得更长,给解决比赛的人带来恐惧,Katya 提出了以下 k 个相同类型的限制(限制中的字符可以重复,有些限制可能会相互矛盾):
- 字符串中的字符数 c1 不小于 l1 且不大于 r1。
- ...
- 字符串中的字符数 ci 不小于 li 且不大于 ri。
- ...
- 字符串中的字符数 ck 不小于 lk 且不大于 rk。
然而,Katya 认为它过于简单和明显,因此添加了以下条件:字符串满足上述给定列表中不少于 L 且不多于 R 的约束。
Katya 不喜欢编写困难且刻薄的测试,因此她只使用一个大字符串 s 并希望将其所有满足约束的子字符串添加到测试中。然而,Katya 迷失在她的条件中,要求你统计字符串 s 中满足条件的子串的个数(子串的每次出现都单独统计)。
输入
第一行包含一个非空字符串 s,由小拉丁字母组成。字符串s的长度不超过105。
第二行包含三个空格分隔的整数 k、L 和 R (0 ≤ L ≤ R ≤ k ≤ 500)。
接下来的 k 行包含 Katya 的缩略语,形式为“ci li ri”。所有字母 ci 都是小拉丁字母,li 和 ri 是整数(0 ≤ li ≤ ri ≤ |s|,其中 |s| 是字符串 s 的长度)。字母 ci 不一定不同。
输出
打印单个数字 — 满足限制条件的子字符串的数量。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cout 流或 %I64d 指定符。
示例
输入 #1
codeforces 2 0 0 o 1 2 e 1 2
输出 #1
7
输入 #2
codeforces 2 1 1 o 1 2 o 1 2
输出 #2
0
注意
在第一个测试中,我们应该计算不包含字符“e”和“o”的字符串的数量。所有此类字符串如下(按照初始字符串中从左到右出现的顺序):“c”、“d”'、“f”、“r”、“rc”、“c”、“s”。
在第二个测试中,我们无法完全满足两个相同限制之一,因此答案为 0。