题目描述

给定一个主串 $s$，以及 $n$ 条规则。每条规则由一个字符串 $p$ 和两个整数 $l,r$ 组成，记作 $(p,l,r)$。

对于任意非空字符串 $t$，定义它在字符串 $p$ 中的出现次数为满足下列条件的区间对 $(L,R)$ 的个数：

不同位置的相同出现分别计数，允许两次出现相互重叠。

如果 $t$ 在 $p$ 中的出现次数位于闭区间 $[l,r]$ 内，则称 $t$ 满足规则 $(p,l,r)$。当 $t$ 满足全部 $n$ 条规则时，称 $t$ 为一个好字符串。

请计算字符串 $s$ 的不同非空子串中，有多少个是好字符串。两个子串只有在字符串内容不同的时候才视为不同；即使它们在 $s$ 中的起止位置不同，只要内容相同，也只计数一次。

输入格式

第一行输入字符串 $s$。

第二行输入整数 $n$。

接下来 $n$ 行，每行输入一个规则：一个字符串 $p_i$ 和两个整数 $l_i,r_i$，三者之间以单个空格分隔。

所有字符串均非空且只包含小写英文字母。保证：

输出格式

输出一个整数，表示 $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

说明

样例 1 中，好子串为 aab、ab 和 b。

样例 2 中，好子串为 e 和 t。