CF1477B.Nezzar and Binary String

Nezzar has a binary string $s$ of length $n$ that he wants to share with his best friend, Nanako. Nanako will spend $q$ days inspecting the binary string. At the same time, Nezzar wants to change the string $s$ into string $f$ during these $q$ days, because it looks better.

It is known that Nanako loves consistency so much. On the $i$-th day, Nanako will inspect a segment of string $s$ from position $l_i$ to position $r_i$ inclusive. If the segment contains both characters '0' and '1', Nanako becomes unhappy and throws away the string.

After this inspection, at the $i$-th night, Nezzar can secretly change strictly less than half of the characters in the segment from $l_i$ to $r_i$ inclusive, otherwise the change will be too obvious.

Now Nezzar wonders, if it is possible to avoid Nanako being unhappy and at the same time have the string become equal to the string $f$ at the end of these $q$ days and nights.

Nezzar 有一个长度为 $n$ 的二进制字符串 $s$，他想将其分享给他的好朋友 Nanako。Nanako 将花费 $q$ 天时间来检查该二进制字符串。与此同时，Nezzar 希望在这 $q$ 天内将字符串 $s$ 变为字符串 $f$，因为 $f$ 看起来更美观。

已知 Nanako 非常喜爱一致性。在第 $i$ 天，Nanako 将检查字符串 $s$ 中从位置 $l_i$ 到位置 $r_i$（含端点）的子段。如果该子段中同时包含字符 '0' 和 '1'，Nanako 就会不开心，并将该字符串丢弃。

在此检查之后，在第 $i$ 天晚上，Nezzar 可以秘密地修改该子段（即从 $l_i$ 到 $r_i$，含端点）中严格少于一半的字符；否则，改动将过于明显。

现在 Nezzar 想知道：是否有可能既避免 Nanako 不开心，又使得经过这 $q$ 天及夜晚的操作后，字符串最终恰好变为字符串 $f$？

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases.

The first line of each test case contains two integers $n,q$ ($1 \le n \le 2 \cdot 10^5$, $0 \le q \le 2 \cdot 10^5$).

The second line of each test case contains a binary string $s$ of length $n$.

The third line of each test case contains a binary string $f$ of length $n$.

Then $q$ lines follow, $i$-th of them contains two integers $l_i,r_i$ ($1 \le l_i \le r_i \le n$) — bounds of the segment, that Nanako will inspect on the $i$-th day.

It is guaranteed that the sum of $n$ for all test cases doesn't exceed $2 \cdot 10^5$, and the sum of $q$ for all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print "YES" on the single line if it is possible to avoid Nanako being unhappy and have the string $f$ at the end of $q$ days and nights. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

对于每个测试用例，如果能够在 $q$ 天 $q$ 夜后避免 Nanako 不开心，并使得字符串 $f$ 成为最终结果，则在单独一行输出 "YES"；否则输出 "NO"。

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

In the first test case, $\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111$ is one of the possible sequences of string changes.

In the second test case, it can be shown that it is impossible to have the string $f$ at the end.

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

在第二个测试用例中，可以证明最终无法得到字符串 $f$。