Migrated from Lutece 2616 easy string problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个串 $S$ 和 $Q$ 组询问，每次询问包含一个字符串 $T$ 和两个数字 $l$，$r$。 每次询问 $T$ 中有多少个本质不同子串不是 $S[l\ldots r]$ 的子串。

Input

第一行一个串 $S$； 第二行一个数 $Q$ 代表询问数； 接下来 $Q$ 行，每行包括一个字符串 $T$ 和两个整数 $l,r$。

Output

对每个询问输出一行一个整数代表答案。

Samples

sugar
6
sua 1 5
a 4 4
a 1 1
sugariv 1 5
aaa 2 5
henghengaaaaa 1 5

2
0
1
13
2
68

Constraints

$1\leq |S|,|T|\leq 5\times 10^5$ $1\leq Q\leq 10^5$ $1\leq \sum |T|\leq 10^6$ 所有字符串中只包含小写英文字母。

Resources

2021 UESTC ICPC Training for String and Search Algorithm