题目描述

Nezzar 有一个长度为 $n$ 的二进制字符串 $s$，他想把它分享给他最好的朋友 Nanako。Nanako 会花费 $q$ 天来检查这个二进制字符串。与此同时，Nezzar 想在这 $q$ 天内把字符串 $s$ 变成字符串 $f$，因为它看起来更好。

已知 Nanako 非常喜欢一致性。在第 $i$ 天，Nanako 会检查字符串 $s$ 中从位置 $l_i$ 到位置 $r_i$（包含两端）的一个片段。如果这个片段同时包含字符 '0' 和 '1'，Nanako 就会不高兴并把字符串扔掉。

在这次检查之后，在第 $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"。

你可以以任意大小写输出每个字母（大写或小写均可）。

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

YES
NO
YES
NO

提示

在第一个测试用例中，$\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111$ 是一种可能的字符串变化序列。

在第二个测试用例中，可以证明不可能在最后得到字符串 $f$。