AT_abc477_c [ABC477C] 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`.

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 $ 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.

### Sample Explanation 1 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.