# 疯狂的串串

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一支小队完成几何练习的任务后，在一家烤串店用餐。餐桌上各色食材排成一串，让他们想起新收到的字符串查询订单：需要在一段串中找出指定模式出现了几次。

## 形式化问题描述

给定仅含小写英文字母的字符串 $S$ ，位置从 $1$ 到 $|S|$ 编号。每次查询给定整数 $l,r$ 和非空字符串 $t$ ，统计 $t$ 在子串 $S_lS_{l+1}\cdots S_r$ 中的出现次数。

一次出现必须完整位于 $[l,r]$ 内。起始位置不同就算不同的一次出现，允许两次出现部分重叠。若模式串比查询区间长，答案为零。

![aba 在 aaababa 中的两次重叠出现](assets/overlaps.svg)

在整个串 `aaababa` 中，`aba` 出现在 $[3,5]$ 和 $[5,7]$ ，共两次。

## 输入格式

第一行字符串 $S$ . 第二行整数 $M$ ，表示查询数。接下来 $M$ 行，每行两个整数 $l,r$ 和一个字符串 $t$ ，以空格分隔。

## 输出格式

输出 $M$ 行，每行一个整数，表示对应查询的出现次数。

## 样例

### 样例 1

### 输入

```text
aaababa
6
1 2 aa
1 7 aba
3 6 aba
4 7 aba
1 3 aa
1 7 c
```

### 输出

```text
1
2
1
1
2
0
```

### 样例 2

### 输入

```text
aaaaa
5
1 5 aaa
2 4 aaaa
1 5 a
2 4 aa
1 1 aa
```

### 输出

```text
3
0
5
2
0
```

### 样例 3

### 输入

```text
abcdef
3
1 6 xyz
1 3 abc
2 6 abc
```

### 输出

```text
0
1
0
```

## 样例解释

样例 1 中，查询 $[3,6]$ 时只有从位置 $3$ 开始的 `aba` 完整位于区间中；从位置 $5$ 开始的那次超出了右端点。

样例 2 的 `aaa` 在 `aaaaa` 中有三次重叠出现；在长度为三的区间中查找 `aaaa` 则得到零。

## 数据范围与保证

对 100% 的数据：$1\le l\le r\le |S|\le1000$ ，$1\le M\le1000$ ，$1\le|t|\le40$ . $S$ 与所有 $t$ 都只含小写英文字母。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |