题目描述

回文字符串是指正读反读都相同的字符串。例如 abba 和 level 都是回文串。

给定一个长度为 $n$ 的字符串 $s$。请回答以下 $Q$ 个查询：

• 第 $i$ 个查询：$s[l_i,r_i]$ 是否为回文串？

其中，$s[l,r]$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符的连续子串。

输入格式

第一行输入正整数 $n,Q$。

第二行输入字符串$s$。

接下来输入$Q$行，每一行包含两个正整数$l_i,r_i(1\le l_i\le r_i\le n)$，表示查询的区间。

输出格式

输出 $Q$ 行。第 $i$ 行对应第 $i$ 个查询的结果：若是回文串则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

6 6
abacaa
1 3
3 5
3 3
2 4
5 6
1 6

输出 #1

YES
YES
YES
NO
YES
NO

【数据范围】

$1 \le n \le 5 \cdot 10^3,\ 1\le Q\le 2\cdot 10^5$