← 返回题目列表

Codeforces · 1451/B

B. 非子串子序列

中文机器翻译题面 查看原题

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") 是一个合适的好子序列。