AT_abc477_c.Range Search Query

You are given strings $S$ and $T$.
Process $Q$ queries.
In each query, you are given $L$ and $R$. Determine whether the substring of $S$ consisting of the $L$-th through $R$-th characters contains $T$ as a substring.

What is a substring? A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, ab is a substring of abc, but ac is not a substring of abc.

给你两个字符串 $S$ 和 $T$。
你需要处理 $Q$ 个查询。
对于每个查询，给定 $L$ 和 $R$，判断 $S$ 中从第 $L$ 个字符到第 $R$ 个字符构成的子串是否包含 $T$ 作为其子串。

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

The input is given from Standard Input in the following format:

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

Each query $\mathrm{query}_q$ is given in the following format:

$L$ $R$

输入从标准输入中按以下格式给出：

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

每个查询 $\mathrm{query}_q$ 的格式如下：

$L$ $R$

Output $Q$ lines. The $q$-th line should contain Yes if, for the $q$-th query, the substring of $S$ consisting of the $L$-th through $R$-th characters contains $T$ as a substring, and No otherwise.

输出 $Q$ 行。对于第 $q$ 个查询，若字符串 $S$ 中从第 $L$ 个字符到第 $R$ 个字符构成的子串包含 $T$ 作为其子串，则第 $q$ 行输出 Yes，否则输出 No。

Sample 1 Explanation:
Consider the first query. The substring of $S$ consisting of the $2$-nd through $6$-th characters is bcdab. The substring of bcdab consisting of the $1$-st through $2$-nd characters matches $T$, so bcdab contains $T$. Thus, the answer is Yes.

Constraints

• $S$ is a string of length between $1$ and $4 \times 10^5$, inclusive, consisting of lowercase English letters.
• $T$ is a string of length between $1$ and $10$, inclusive, consisting of lowercase English letters.
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L \leq R \leq |S|$
• $Q, L, R$ are integers.

样例 1 解释：
考虑第一个查询。字符串 $S$ 中第 $2$ 个到第 $6$ 个字符组成的子串为 bcdab。该子串 bcdab 中第 $1$ 个到第 $2$ 个字符组成的子串与 $T$ 相匹配，因此 bcdab 包含 $T$。故答案为 Yes。

约束条件

• $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$ 均为整数。