407658: GYM102864 I shenyunhan Loves Palindrome

奋战三星期，造台计算机。

shenyunhan has made a computer. This computer is special, it can determine whether a substring of some template string is a cyclic palindrome.

Now shenyunhan wants to verify his computer. shenyunhan will give you a template string $$$s$$$ and some questions. For each question, shenyunhan wants to know whether some substring of $$$s$$$ is cyclic palindrome.

A string $$$s$$$ of length $$$n$$$ is palindrome if and only if the following condition holds:

$$$$$$ \left(\forall i \in \left[1,n\right]\right) \left(s\left[i\right] = s\left[n-i+1\right]\right) $$$$$$

A string $$$s$$$ of length $$$n$$$ is cyclic palindrome if and only if the following condition holds:

$$$$$$ \left(\exists N \in \left[n, 2n-1\right]\right) \left( \left(\forall i \in \left[1, N\right]\right) \left(s\left[\left(i-1\right) \;\mathrm{mod}\; n +1\right] = s\left[\left(N-i\right) \;\mathrm{mod}\; n +1\right]\right) \right) $$$$$$

Note that string indexes starts from $$$1$$$.

It's obvious that all palindromes are cyclic palindromes.

The first line of input contains two space seperated integers $$$n$$$ and $$$q$$$ $$$\left(1 \le n,q \le 2 \times 10^5\right)$$$. $$$n$$$ is the length of the template string and $$$q$$$ is the number of questions shenyunhan is going to ask you.

The next line contains the template string $$$s$$$ of length $$$n$$$. It's guaranteed that all characters in $$$s$$$ are lowercase English letters.

For the next $$$q$$$ lines, the $$$i$$$-th line contains two space seperated integer $$$l_i$$$ and $$$r_i$$$ $$$\left(1 \le l_i \le r_i \le n\right)$$$ which represents the $$$i$$$-th question that shenyunhan asks you. Your program needs to figure out whether the substring $$$s\left[l_i..r_i\right]$$$ is a cyclic palindrome.

The notation $$$s\left[L..R\right]$$$ represents the substring of $$$s$$$ that spans from the character at index $$$L$$$ to the character at index $$$R$$$, inclusive. For example, $$$\mathrm{hello}\left[2..4\right] = \mathrm{ell}$$$. Note that string indexes start from $$$1$$$.

For each question asked by shenyunhan, please output the answer on a seperate line. For the $$$i$$$-th question, if the substring $$$s\left[l_i..r_i\right]$$$ is a cyclic palindrome, output YES; otherwise output NO.

The judge is case-insensitive, so you can output your answer in any case you wish.

10 6
bbccbcbbac
8 10
1 10
9 9
9 10
4 6
1 7

NO
NO
YES
YES
YES
NO

In the given example test case:

• For the first query, $$$s\left[8..10\right] = \mathrm{bac}$$$, which is not a cyclic palindrome;
• For the second query, $$$s\left[1..10\right] = \mathrm{bbccbcbbac}$$$, which is not a cyclic palindrome;
• For the third query, $$$s\left[9..9\right] = \mathrm{a}$$$, which is a cyclic palindrome since it's a palindrome;
• For the forth query, $$$s\left[9..10\right] = \mathrm{ac}$$$, which is a cyclic palindrome;
• For the fifth query, $$$s\left[4..6\right] = \mathrm{cbc}$$$, which is a cyclic palindrome since it's a palindrome;
• For the sixth query, $$$s\left[1..7\right] = \mathrm{bbccbcb}$$$, which is not a cyclic palindrome.