CF316G3.Good Substrings

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].

聪明的海狸最近对一种新的单词游戏产生了兴趣。游戏规则如下：统计字符串 $s$ 中不同“好”子串的数量。要判断一个字符串是否为“好”串，需依据若干条规则。总共有 $n$ 条规则，每条规则由一个三元组 $(p,\,l,\,r)$ 描述，其中 $p$ 是一个字符串，$l$ 和 $r$（满足 $l \le r$）是整数。我们称字符串 $t$ 符合规则 $(p,\,l,\,r)$，当且仅当 $t$ 在字符串 $p$ 中的出现次数介于 $l$ 与 $r$ 之间（含端点）。例如，字符串 "ab" 符合规则 ("ab", 1, 2) 和 ("aab", 0, 1)，但不符合规则 ("cd", 1, 2) 和 ("abab", 0, 1)。

字符串 $s = s_1 s_2 \dots s_{|s|}$（其中 $|s|$ 表示 $s$ 的长度）的一个子串 $s[l \dots r]$（满足 $1 \le l \le r \le |s|$）定义为字符串 $s_l s_{l+1} \dots s_r$。

我们将字符串 $t$ 在字符串 $p$ 中的出现次数定义为满足 $p[l \dots r] = t$ 的整数对 $(l,\,r)$（其中 $1 \le l \le r \le |p|$）的个数。

若字符串 $t$ 符合全部 $n$ 条规则，则称其为好串。聪明的海狸请你帮他编写一个程序，计算字符串 $s$ 中不同好子串的个数。两个子串 $s[x \dots y]$ 与 $s[z \dots w]$ 被视为不同，当且仅当 $s[x \dots y] \ne s[z \dots 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.

第一行包含字符串 $s$。第二行包含整数 $n$。接下来的 $n$ 行每行包含一条规则。每行包含一个字符串和两个整数 $p_i$、$l_i$、$r_i$，以单个空格分隔（满足 $0 \le l_i \le r_i \le |p_i|$）。保证所有给定字符串均非空，且仅由小写英文字母组成。

得分为 30 分的输入限制（子问题 G1）：

• $0 \le n \le 10$。
• 字符串 $s$ 的长度以及字符串 $p$ 的最大长度均 $\le 200$。

得分为 70 分的输入限制（子问题 G1+G2）：

• $0 \le n \le 10$。
• 字符串 $s$ 的长度以及字符串 $p$ 的最大长度均 $\le 2000$。

得分为 100 分的输入限制（子问题 G1+G2+G3）：

• $0 \le n \le 10$。
• 字符串 $s$ 的长度以及字符串 $p$ 的最大长度均 $\le 50000$。

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

输出一个整数——字符串 $s$ 中“好”子串的个数。

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.

第一个样例测试中有三个“好”子串：«aab»、«ab» 和 «b»。

第二个测试中，仅有子串 «e» 和 «t» 是“好”的。