← 返回题目列表

Codeforces · 1477/B

B. Nezzar 和二进制字符串

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

Nezzar 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,他想与他最好的朋友 Nanako 分享。 Nanako 将花费 $$$q$$$ 天检查二进制字符串。同时,Nezzar 希望在这 $$$q$$$ 天内将字符串 $$$s$$$ 更改为字符串 $$$f$$$,因为这样看起来更好。

众所周知,菜菜子非常喜欢一致性。在第 $$$i$$$ 天,Nanako 将检查 $$$s$$$ 中从位置 $$$l_i$$$ 到位置 $$$r_i$$$(含)的一段字符串。如果该段同时包含字符“0”和“1”,菜菜子会变得不高兴并扔掉该字符串。

经过这次检查,在第 $$$i$$$ 个晚上,Nezzar 可以秘密地严格将段中从 $$$l_i$$$ 到 $$$r_i$$$ 的字符少于一半更改,否则更改将太明显。

现在 Nezzar 想知道,是否有可能避免 Nanako 不高兴,同时让字符串在这些 $$$q$$$ 日日夜夜结束时变得等于字符串 $$$f$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n,q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。

每个测试用例的第三行包含一个长度为$$$n$$$的二进制字符串$$$f$$$。

然后是 $$$q$$$ 行,其中 $$$i$$$ 包含两个整数 $$$l_i,r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 段的边界,Nanako 将在第 $$$i$$$ 天检查。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以避免 Nanako 不高兴,并在 $$$q$$$ 日日夜夜的末尾添加字符串 $$$f$$$,则在单行上打印“YES”。否则,打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

4
5 2
00000
00111
1 5
1 3
2 1
00
01
1 2
10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10
5 2
10000
11000
2 5
1 3

输出 #1

YES
NO
YES
NO

注意

在第一个测试用例中, $$$\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111$$$ 是字符串更改的可能序列之一。

在第二个测试用例中,可以表明末尾不可能有字符串 $$$f$$$。