题目描述

给定字符串 $S$ 和 $T$。请处理 $Q$ 个询问。 每个询问给定 $L$ 和 $R$，判断由 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的子串是否包含 $T$ 作为子串。

什么是子串？$S$ 的子串是指从 $S$ 的开头删除零个或多个字符，并从 $S$ 的末尾删除零个或多个字符后得到的字符串。 例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

输入按以下格式从标准输入读入：

• $Q$
• $S$
• $T$
• $\mathrm{query}_1$
• $\mathrm{query}_2$
• $\vdots$
• $\mathrm{query}_Q$

每个询问 $\mathrm{query}_q$ 按以下格式给出：

• $L$ $R$

输出格式

输出 $Q$ 行。第 $q$ 行：若由 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的子串包含 $T$ 作为子串，则输出 Yes，否则输出 No。

3
abcdabc
bc
2 6
3 5
3 7

Yes
No
Yes

考虑第 $1$ 个询问。由 $S$ 的第 $2$ 个字符到第 $6$ 个字符组成的子串是 bcdab。由 bcdab 的第 $1$ 个字符到第 $2$ 个字符组成的子串与 $T$ 相同，因此 bcdab 包含 $T$。所以答案为 Yes。

10
bbbaaabbbaaaaaabbbab
bbb
5 16
5 6
2 16
6 7
17 19
3 7
7 16
7 20
17 19
2 6

Yes
No
Yes
No
No
No
Yes
Yes
No
No

数据范围

• $S$ 是长度在 $1$ 到 $4 \times 10^5$ 之间（含两端）的、由小写英文字母组成的字符串。

• $T$ 是长度在 $1$ 到 $10$ 之间（含两端）的、由小写英文字母组成的字符串。

• $1 \leq Q \leq 2 \times 10^5$

• $1 \leq L \leq R \leq |S|$

• $Q, L, R$ 均为整数。

• 来源：AtCoder ABC 477 C

子任务设置

• 子任务 1（30 分）：$|S|, Q \le 2000$。
• 子任务 2（70 分）：无特殊限制。