题目描述

给定 $k$ 个限制条件，其中第 $i$ 个条件用 $c_i,l_i,r_i$ 表示：

字符 $c_i$ 在字符串中的出现次数大于等于 $l_i$，小于等于 $r_i$。

若一个字符串满足的限制条件的个数大于等于 $L$，小于等于 $R$，则称该串为 Stenis String。

给定一小写字母串 $s$ ，求 $s$ 有多少个子串是 Steins String。

输入格式

第一行一个非空的小写字母串 $s$。
第二行三个整数 $k,L,R$。
以下 $k$ 行，每行一个字符和两个整数表示 $c_i,l_i,r_i$。

输出格式

一个整数，表示答案。

elpsycongroo
3 1 2
o 2 4
a 1 2
y 1 3

48

数据规模与约定

对于 $100\%$ 的数据，$0 \le L \le R \le k \le 500$，$0 \le l_i \le r_i \le |s|$，$|s| \le 10^5$。