题目描述

智能海狸最近对一种新单词游戏产生了兴趣。要点如下：计算某个字符串 $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[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]$，则认为它们是不同的。

输入

第一行包含字符串 $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$。

输出

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

样例

样例 1

输入：

aaab
2
aa 0 0
aab 1 1

输出：

3

样例 2

输入：

ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1

输出：

2

样例 3

输入：

a
0

输出：

1

样例解释

在第一个样例中，好的子串有三个："aab"、"ab" 和 "b"。
在第二个样例中，只有子串 "e" 和 "t" 是好的。