Codeforces Round 698 (Div. 1) |
---|
Закончено |
У 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$$$ в конце.
Название |
---|