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.