E. Nezzar и бинарная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Nezzar есть бинарная строка $$$s$$$ длины $$$n$$$, которой он хочет поделиться со своим лучшим другом, Nanako. Он будет в течение $$$q$$$ дней проверять эту бинарную строку. В то же время Nezzar хочет изменить свою строку $$$s$$$ так, чтобы она через $$$q$$$ дней стала равна более красивой строке $$$f$$$.

Известно, что Nanako очень любит однообразие. В $$$i$$$-й день Nanako будет проверять отрезок строки $$$s$$$ с позиции $$$l_i$$$ по позицию $$$r_i$$$ включительно. Если на этом отрезке есть символы и «0», и «1», Nanako очень расстроится и выкинет строку.

После каждой проверки, в $$$i$$$-ю ночь Nezzar может тайно поменять строго меньше, чем половину символов на отрезке с $$$l_i$$$ по $$$r_i$$$ включительно (потому что иначе изменение будет слишком очевидным).

Сейчас Nezzar интересуется, можно ли избежать того, что Nanako расстроится, и вместе с этим получить строку $$$f$$$ в конце этих $$$q$$$ дней и ночей.

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

В первой строке находится единственное целое число $$$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$$$).

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

В третьей строке описания каждого набора входных данных находится бинарная строка $$$f$$$ длины $$$n$$$.

Затем следуют $$$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$$$.

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

Для каждого набора входных данных в собственной строке выведите «YES», если можно избежать того, что Nanako расстроится, и получить строку $$$f$$$ в конце $$$q$$$ дней и ночей. Иначе выведите «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$$$ в конце.