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$$$。