Hr0d1y 对长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 进行了 $$$q$$$ 查询。二进制字符串是仅包含字符“0”和“1”的字符串。
查询由一对整数 $$$l_i$$$、$$$r_i$$$ $$$(1 \leq l_i \lt r_i \leq n)$$$ 描述。
对于每个查询,他必须确定 $$$s$$$ 中是否存在等于子字符串 $$$s[l_i\ldots r_i]$$$ 的好子序列。
- 字符串 $$$s$$$ 的子字符串 $$$s[i\ldots j]$$$ 是由字符 $$$s_i s_{i+1} \ldots s_j$$$ 形成的字符串。
- 如果通过删除一些字符而不改变剩余字符的顺序可以从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 被认为是字符串 $$$b$$$ 的子序列。
- 如果子序列不连续并且长度为 $$$\ge 2$$$,则称该子序列是好的。例如,如果 $$$s$$$ 是“1100110”,则子序列 $$$s_1s_2s_4$$$ ("1100110") 和 $$$s_1s_5s_7$$$ ("1100110") 是好的,而 $$$s_1s_2s_3$$$ ("1100110") 则不好。
你能帮助 Hr0d1y 回答每个问题吗?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 100$$$) — 测试用例的数量。每个测试用例的描述如下。
第一行包含两个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) 和 $$$q$$$ ($$$1\leq q \leq 100$$$) - 字符串的长度和查询的数量。
第二行包含字符串$$$s$$$。
接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$)。
输出
对于每个测试用例,输出 $$$q$$$ 行。如果存在等于子串 $$$s[l_i...r_i]$$$ 的好子序列,则每个测试用例输出的第 $$$i$$$ 行应包含“YES”,否则应包含“NO”。
您可以以任何大小写方式打印每个字母(大写或小写)。
示例
输入 #1
2 6 3 001000 2 4 1 3 3 5 4 2 1111 1 4 2 3
输出 #1
YES NO YES NO YES
注意
在第一个测试用例中,
- $$$s[2\ldots 4] = $$$“010”。在这种情况下,$$$s_1s_3s_5$$$(“001000”)和$$$s_2s_3s_6$$$(“001000”)是很好的合适子序列,而$$$s_2s_3s_4$$$(“001000”)则不好。
- $$$s[1\ldots 3] = $$$“001”。不存在合适的好子序列。
- $$$s[3\ldots 5] = $$$“100”。这里 $$$s_3s_5s_6$$$ ("001000") 是一个合适的好子序列。