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

Дано две строки равной длины $$$s_1$$$ и $$$s_2$$$, состоящие из строчных букв латинского алфавита, и натуральное число $$$t$$$.

Вам необходимо ответить на $$$q$$$ запросов, пронумерованных от $$$1$$$ до $$$q$$$. $$$i$$$-й запрос приходит в $$$i$$$-ю секунду времени. Каждый запрос одного из трёх типов:

  • заблокировать символы на позиции $$$pos$$$ (индексация с $$$1$$$) в обеих строках на $$$t$$$ секунд;
  • поменять местами два не заблокированных символа;
  • сказать, равны ли на момент запроса две строки без учёта заблокированных символов.

Заметьте, в запросах второго типа местами могут менять как символы, принадлежащие одной строке, так и символ из $$$s_1$$$ с символом из $$$s_2$$$.

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

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

Далее следуют описания наборов.

В первой строке набора содержится строка $$$s_1$$$, состоящая из строчных букв латинского алфавита (длины не более $$$2 \cdot 10^5$$$).

Во второй строке набора содержится строка $$$s_2$$$, состоящая из строчных букв латинского алфавита (длины не более $$$2 \cdot 10^5$$$).

Строки имеют равную длину.

В третьей строке набора содержатся два натуральных числа $$$t$$$ и $$$q$$$ ($$$1 \le t, q \le 2 \cdot 10^5$$$). Число $$$t$$$ означает количество секунд, на которые блокируется символ. Число $$$q$$$ соответствует количеству запросов.

В каждой из следующих $$$q$$$ строк набора содержатся сами запросы — по одному в строке. Каждый запрос одного из трёх типов:

  • «$$$1\ \ \ pos$$$» — заблокировать символы на позиции $$$pos$$$ в обеих строках на $$$t$$$ секунд;
  • «$$$2\ \ \ 1/\;\!2\ \ \ pos_1\ \ \ 1/\;\!2\ \ \ pos_2$$$» — поменять местами два не заблокированных символа. Второе число в запросе указывает номер строки, из которой берётся первый символ для обмена. Третье число в запросе указывает позицию в строке этого символа. Четвёртое число в запросе указывает номер строки, из которой берётся второй символ для обмена. Пятое число в запросе указывает позицию в строке этого символа;
  • «$$$3$$$» — запрос равенства двух строк без учёта заблокированных символов.

Для запросов первого типа гарантируется, что на момент запроса символы на позиции $$$pos$$$ не заблокированы.

Для запросов второго типа гарантируется, что меняющиеся местами символы не заблокированы.

Все значения $$$pos, pos_1, pos_2$$$ лежат в диапазоне от $$$1$$$ до длин строк.

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

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

Для каждого запроса третьего типа выведите «YES», если на момент запроса строки $$$s_1$$$ и $$$s_2$$$ равны без учёта заблокированных символов, «NO» — иначе.

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

Пример
Входные данные
2
codeforces
codeblocks
5 7
3
1 5
1 6
1 7
1 9
3
3
cool
club
2 5
2 1 2 2 3
2 2 2 2 4
1 2
3
3
Выходные данные
NO
YES
NO
YES
NO
Примечание

Давайте посмотрим на строки $$$s_1$$$ и $$$s_2$$$ после каждого из $$$q$$$ запросов. Будем обозначать красным цветом заблокированные символы.

Первый пример входных данных:

($$$codeforces$$$, $$$codeblocks$$$) $$$\rightarrow$$$ ($$$codeforces$$$, $$$codeblocks$$$) $$$\rightarrow$$$ ($$$code\color{red}{f}orces$$$, $$$code\color{red}{b}locks$$$) $$$\rightarrow$$$ ($$$code\color{red}{fo}rces$$$, $$$code\color{red}{bl}ocks$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}ces$$$, $$$code\color{red}{blo}cks$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}c\color{red}{e}s$$$, $$$code\color{red}{blo}c\color{red}{k}s$$$) $$$\rightarrow$$$ ($$$code\color{red}{for}c\color{red}{e}s$$$, $$$code\color{red}{blo}c\color{red}{k}s$$$) $$$\rightarrow$$$ ($$$codef\color{red}{or}c\color{red}{e}s$$$, $$$codeb\color{red}{lo}c\color{red}{k}s$$$)

Второй пример входных данных:

($$$cool$$$, $$$club$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$clob$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$cbol$$$) $$$\rightarrow$$$ ($$$c\color{red}{u}ol$$$, $$$c\color{red}{b}ol$$$) $$$\rightarrow$$$ ($$$c\color{red}{u}ol$$$, $$$c\color{red}{b}ol$$$) $$$\rightarrow$$$ ($$$cuol$$$, $$$cbol$$$)