CF2248D.Good Pair Queries

You are given two binary strings $s$ and $t$, both of length $n$.

For two binary strings $a$ and $b$ of the same length, the pair $(a, b)$ is called good if both strings can be made empty by performing the following operation zero or more times:

• Choose a non-empty set of positions $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ and a character $c \in {\mathtt{0}, \mathtt{1}}$.
• Let $x = a_{i_1}a_{i_2}\ldots a_{i_k}$ and $y = b_{i_1}b_{i_2}\ldots b_{i_k}$.
• The character $c$ must be a mode$^{\text{∗}}$ of both $x$ and $y$.
• Delete the characters at the chosen positions from both strings. The remaining characters are concatenated without changing their relative order.

A binary string may have both $\mathtt{0}$ and $\mathtt{1}$ as modes.

You need to answer $q$ queries. In each query, you are given two integers $l$ and $r$. Determine whether the pair of substrings $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good.

The queries are independent.

$^{\text{∗}}$For a binary string $z$, a character $c$ is a mode if it appears at least $\left\lceil \frac{|z|}{2} \right\rceil$ times in $z$. Here, $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$.

给你两个长度均为 $n$ 的二进制字符串 $s$ 和 $t$。

对于两个等长的二进制字符串 $a$ 和 $b$，若可通过执行以下操作零次或多次使两个字符串均变为空，则称数对 $(a, b)$ 是好的：

• 选择一个非空的位置集合 $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ 以及一个字符 $c \in {\mathtt{0}, \mathtt{1}}$；
• 令 $x = a_{i_1}a_{i_2}\ldots a_{i_k}$，$y = b_{i_1}b_{i_2}\ldots b_{i_k}$；
• 字符 $c$ 必须同时是 $x$ 和 $y$ 的众数$^{\text{∗}}$；
• 从两个字符串中同时删除所选位置上的字符；剩余字符保持原有相对顺序拼接。

一个二进制字符串可能同时以 $\mathtt{0}$ 和 $\mathtt{1}$ 为众数。

你需要回答 $q$ 个查询。每次查询给出两个整数 $l$ 和 $r$，判断子串对 $(s_l s_{l+1} \ldots s_r,\; t_l t_{l+1} \ldots t_r)$ 是否为好的。

各查询相互独立。

$^{\text{∗}}$ 对于二进制字符串 $z$，字符 $c$ 是其众数，当且仅当 $c$ 在 $z$ 中出现次数至少为 $\left\lceil \frac{|z|}{2} \right\rceil$。其中 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of each string and the number of queries.

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

The third line of each test case contains the binary string $t$ of length $n$.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — a query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别表示每个字符串的长度以及查询次数。

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

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

接下来的 $q$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）—— 表示一次查询。

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

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

For each query, output "YES" if the pair $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个查询，若数对 $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ 是“好”的，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

In the first test case, for the first query, the pair is $(\mathtt{0}, \mathtt{1})$. No character is a mode of both strings, so no operation can be performed.

For the second query, choose both positions and $c = \mathtt{0}$. Then $x = \mathtt{01}$ and $y = \mathtt{10}$, so $c$ is a mode of both strings and the whole pair is deleted.

In the third test case, neither character is a mode of both $\mathtt{00011}$ and $\mathtt{01111}$, so the whole pair cannot be deleted in one operation. It can be emptied in three operations:

• Choose positions $2$ and $4$ and $c = \mathtt{1}$. Then $x = \mathtt{01}$ and $y = \mathtt{11}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the remaining characters are concatenated, giving the pair $(\mathtt{001}, \mathtt{011})$.
• Choose positions $1$ and $2$ and $c = \mathtt{0}$. Then $x = \mathtt{00}$ and $y = \mathtt{01}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the pair becomes $(\mathtt{1}, \mathtt{1})$.
• Choose the remaining position $1$ and $c = \mathtt{1}$. Then $x = \mathtt{1}$ and $y = \mathtt{1}$, so $c$ is a mode of both $x$ and $y$. Deleting the selected position makes both strings empty.

在第一个测试用例中，对于第一个查询，该数对为 $(\mathtt{0}, \mathtt{1})$。没有任何字符同时是两个字符串的众数，因此无法执行任何操作。

对于第二个查询，选择两个位置，并令 $c = \mathtt{0}$。此时 $x = \mathtt{01}$，$y = \mathtt{10}$，因此 $c$ 是两个字符串的众数，整个数对被删除。

在第三个测试用例中，$\mathtt{00011}$ 和 $\mathtt{01111}$ 中没有任何一个字符同时是这两个字符串的众数，因此整个数对无法通过一次操作删除。但可以通过三次操作将其清空：

• 选择位置 $2$ 和 $4$，并令 $c = \mathtt{1}$。此时 $x = \mathtt{01}$，$y = \mathtt{11}$，因此 $c$ 是 $x$ 和 $y$ 的众数。删除所选位置后，剩余字符被连接，得到新数对 $(\mathtt{001}, \mathtt{011})$。
• 选择位置 $1$ 和 $2$，并令 $c = \mathtt{0}$。此时 $x = \mathtt{00}$，$y = \mathtt{01}$，因此 $c$ 是 $x$ 和 $y$ 的众数。删除所选位置后，数对变为 $(\mathtt{1}, \mathtt{1})$。
• 选择剩余的位置 $1$，并令 $c = \mathtt{1}$。此时 $x = \mathtt{1}$，$y = \mathtt{1}$，因此 $c$ 是 $x$ 和 $y$ 的众数。删除所选位置后，两个字符串均变为空。