← 返回题目列表

Codeforces · 138/E

E. 地狱般的约束

中文机器翻译题面 查看原题

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。