Problem Statement

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.

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.

Input

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$

Output

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.

3
abcdabc
bc
2 6
3 5
3 7

Yes
No
Yes

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.

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

• Source: AtCoder ABC 477 C