D. Запросы хороших пар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две бинарные строки $$$s$$$ и $$$t$$$, обе длины $$$n$$$.

Для двух бинарных строк $$$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$$$ должен быть модой$$$^{\text{∗}}$$$ и для $$$x$$$, и для $$$y$$$.
  • Удалите символы на выбранных позициях из обеих строк. Оставшиеся символы объединяются без изменения их относительного порядка.

Бинарная строка может иметь и $$$\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$$$ называется модой, если он встречается в $$$z$$$ как минимум $$$\left\lceil \frac{|z|}{2} \right\rceil$$$ раз. Здесь $$$\lceil x \rceil$$$ обозначает наименьшее целое число, не меньшее $$$x$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — длину каждой строки и количество запросов.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.

Третья строка каждого набора входных данных содержит бинарную строку $$$t$$$ длины $$$n$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите «YES», если пара $$$(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$$$ является хорошей. Иначе выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
2 2
01
10
1 1
1 2
5 1
11111
11111
1 3
5 1
00011
01111
1 5
Выходные данные
NO
YES
YES
YES
Примечание

В первом наборе входных данных для первого запроса пара равна $$$(\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$$$. После удаления выбранной позиции обе строки становятся пустыми.