Дано две строки равной длины \(s_1\) и \(s_2\), состоящие из строчных букв латинского алфавита, и натуральное число \(t\).
Вам необходимо ответить на \(q\) запросов, пронумерованных от \(1\) до \(q\). \(i\)-й запрос приходит в \(i\)-ю секунду времени. Каждый запрос одного из трёх типов:
- заблокировать символы на позиции \(pos\) (индексация с \(1\)) в обеих строках на \(t\) секунд;
- поменять местами два не заблокированных символа;
- сказать, равны ли на момент запроса две строки без учёта заблокированных символов.
Заметьте, в запросах второго типа местами могут менять как символы, принадлежащие одной строке, так и символ из \(s_1\) с символом из \(s_2\).
Выходные данные
Для каждого запроса третьего типа выведите «YES», если на момент запроса строки \(s_1\) и \(s_2\) равны без учёта заблокированных символов, «NO» — иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Давайте посмотрим на строки \(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\))
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|